Define DefinedAtom::sectionSize.

Merge::mergeByLargestSection is half-baked since it's defined
in terms of section size, there's no way to get the section size
of an atom.

Currently we work around the issue by traversing the layout edges
to both directions and calculate the sum of all atoms reachable.
I wrote that code but I knew it's hacky. It's even not guaranteed
to work. If you add layout edges before the core linking, it
miscalculates a size.

Also it's of course slow. It's basically a linked list traversal.

In this patch I added DefinedAtom::sectionSize so that we can use
that for mergeByLargestSection. I'm not very happy to add a new
field to DefinedAtom base class, but I think it's legitimate since
mergeByLargestSection is defined for section size, and the section
size is currently just missing.

http://reviews.llvm.org/D7966

llvm-svn: 231290

9 files changed, 46 insertions, 59 deletions

diff --git a/lld/include/lld/Core/DefinedAtom.h b/lld/include/lld/Core/DefinedAtom.h
index aaca2042ebf..78f4ac3ede5 100644
--- a/lld/include/lld/Core/DefinedAtom.h
+++ b/lld/include/lld/Core/DefinedAtom.h
@@ -234,6 +234,13 @@ public:
   /// For a function atom, it is the number of bytes of code in the function.
   virtual uint64_t size() const = 0;
 
+  /// \brief The size of the section from which the atom is instantiated.
+  ///
+  /// Merge::mergeByLargestSection is defined in terms of section size
+  /// and not in terms of atom size, so we need this function separate
+  /// from size().
+  virtual uint64_t sectionSize() const { return 0; }
+
   /// \brief The visibility of this atom to other atoms.
   ///
   /// C static functions have scope scopeTranslationUnit.  Regular C functions
diff --git a/lld/lib/Core/SymbolTable.cpp b/lld/lib/Core/SymbolTable.cpp
index b06cdec472f..d264cb78d95 100644
--- a/lld/lib/Core/SymbolTable.cpp
+++ b/lld/lib/Core/SymbolTable.cpp
@@ -133,36 +133,6 @@ static MergeResolution mergeSelect(DefinedAtom::Merge first,
   return mergeCases[first][second];
 }
 
-static const DefinedAtom *followReference(const DefinedAtom *atom,
-                                          uint32_t kind) {
-  for (const Reference *r : *atom)
-    if (r->kindNamespace() == Reference::KindNamespace::all &&
-        r->kindArch() == Reference::KindArch::all &&
-        r->kindValue() == kind)
-      return cast<const DefinedAtom>(r->target());
-  return nullptr;
-}
-
-static uint64_t getSizeFollowReferences(const DefinedAtom *atom,
-                                        uint32_t kind) {
-  uint64_t size = 0;
-  for (;;) {
-    atom = followReference(atom, kind);
-    if (!atom)
-      return size;
-    size += atom->size();
-  }
-}
-
-// Returns the size of the section containing the given atom. Atoms in the same
-// section are connected by layout-before and layout-after edges, so this
-// function traverses them to get the total size of atoms in the same section.
-static uint64_t sectionSize(const DefinedAtom *atom) {
-  return atom->size()
-      + getSizeFollowReferences(atom, lld::Reference::kindLayoutBefore)
-      + getSizeFollowReferences(atom, lld::Reference::kindLayoutAfter);
-}
-
 bool SymbolTable::addByName(const Atom &newAtom) {
   StringRef name = newAtom.name();
   assert(!name.empty());
@@ -198,14 +168,14 @@ bool SymbolTable::addByName(const Atom &newAtom) {
       useNew = true;
       break;
     case MCR_Largest: {
-      uint64_t existingSize = sectionSize(existingDef);
-      uint64_t newSize = sectionSize(newDef);
+      uint64_t existingSize = existingDef->sectionSize();
+      uint64_t newSize = newDef->sectionSize();
       useNew = (newSize >= existingSize);
       break;
     }
     case MCR_SameSize: {
-      uint64_t existingSize = sectionSize(existingDef);
-      uint64_t newSize = sectionSize(newDef);
+      uint64_t existingSize = existingDef->sectionSize();
+      uint64_t newSize = newDef->sectionSize();
       if (existingSize == newSize) {
         useNew = true;
         break;
diff --git a/lld/lib/ReaderWriter/Native/NativeFileFormat.h b/lld/lib/ReaderWriter/Native/NativeFileFormat.h
index 889fd457970..a2e8396812a 100644
--- a/lld/lib/ReaderWriter/Native/NativeFileFormat.h
+++ b/lld/lib/ReaderWriter/Native/NativeFileFormat.h
@@ -136,6 +136,7 @@ struct NativeDefinedAtomIvarsV1 {
   uint32_t  referencesCount;
   uint32_t  contentOffset;
   uint32_t  contentSize;
+  uint64_t  sectionSize;
 };
 
 
diff --git a/lld/lib/ReaderWriter/Native/ReaderNative.cpp b/lld/lib/ReaderWriter/Native/ReaderNative.cpp
index 00160d05f54..5ada70c12ef 100644
--- a/lld/lib/ReaderWriter/Native/ReaderNative.cpp
+++ b/lld/lib/ReaderWriter/Native/ReaderNative.cpp
@@ -45,9 +45,9 @@ public:
 
   StringRef name() const override;
 
-  uint64_t size() const override {
-    return _ivarData->contentSize;
-  }
+  uint64_t size() const override { return _ivarData->contentSize; }
+
+  uint64_t sectionSize() const override { return _ivarData->sectionSize; }
 
   DefinedAtom::Scope scope() const override {
     return (DefinedAtom::Scope)(attributes().scope);
diff --git a/lld/lib/ReaderWriter/Native/WriterNative.cpp b/lld/lib/ReaderWriter/Native/WriterNative.cpp
index 0fe7d21c99a..a3187ccd64a 100644
--- a/lld/lib/ReaderWriter/Native/WriterNative.cpp
+++ b/lld/lib/ReaderWriter/Native/WriterNative.cpp
@@ -126,6 +126,7 @@ private:
     ivar.referencesCount = refsCount;
     ivar.contentOffset = getContentOffset(atom);
     ivar.contentSize = atom.size();
+    ivar.sectionSize = atom.sectionSize();
     _definedAtomIvars.push_back(ivar);
   }
 
diff --git a/lld/lib/ReaderWriter/PECOFF/Atoms.h b/lld/lib/ReaderWriter/PECOFF/Atoms.h
index a5d888c690e..733b9846e1f 100644
--- a/lld/lib/ReaderWriter/PECOFF/Atoms.h
+++ b/lld/lib/ReaderWriter/PECOFF/Atoms.h
@@ -145,11 +145,12 @@ private:
 class COFFDefinedFileAtom : public COFFBaseDefinedAtom {
 public:
   COFFDefinedFileAtom(const File &file, StringRef name, StringRef sectionName,
-                      Scope scope, ContentType contentType,
-                      ContentPermissions perms, uint64_t ordinal)
+                      uint64_t sectionSize, Scope scope,
+                      ContentType contentType, ContentPermissions perms,
+                      uint64_t ordinal)
       : COFFBaseDefinedAtom(file, name, Kind::File), _sectionName(sectionName),
-        _scope(scope), _contentType(contentType), _permissions(perms),
-        _ordinal(ordinal), _alignment(0) {}
+        _sectionSize(sectionSize), _scope(scope), _contentType(contentType),
+        _permissions(perms), _ordinal(ordinal), _alignment(0) {}
 
   static bool classof(const COFFBaseDefinedAtom *atom) {
     return atom->getKind() == Kind::File;
@@ -158,6 +159,7 @@ public:
   void setAlignment(Alignment val) { _alignment = val; }
   SectionChoice sectionChoice() const override { return sectionCustomRequired; }
   StringRef customSectionName() const override { return _sectionName; }
+  uint64_t sectionSize() const override { return _sectionSize; }
   Scope scope() const override { return _scope; }
   ContentType contentType() const override { return _contentType; }
   ContentPermissions permissions() const override { return _permissions; }
@@ -173,6 +175,7 @@ public:
 
 private:
   StringRef _sectionName;
+  uint64_t _sectionSize;
   Scope _scope;
   ContentType _contentType;
   ContentPermissions _permissions;
@@ -185,11 +188,11 @@ private:
 class COFFDefinedAtom : public COFFDefinedFileAtom {
 public:
   COFFDefinedAtom(const File &file, StringRef name, StringRef sectionName,
-                  Scope scope, ContentType type, bool isComdat,
-                  ContentPermissions perms, Merge merge, ArrayRef<uint8_t> data,
-                  uint64_t ordinal)
-      : COFFDefinedFileAtom(file, name, sectionName, scope, type, perms,
-                            ordinal),
+                  uint64_t sectionSize, Scope scope, ContentType type,
+                  bool isComdat, ContentPermissions perms, Merge merge,
+                  ArrayRef<uint8_t> data, uint64_t ordinal)
+      : COFFDefinedFileAtom(file, name, sectionName, sectionSize,
+                            scope, type, perms, ordinal),
         _isComdat(isComdat), _merge(merge), _dataref(data) {}
 
   Merge merge() const override { return _merge; }
@@ -213,8 +216,8 @@ public:
   COFFBSSAtom(const File &file, StringRef name, Scope scope,
               ContentPermissions perms, Merge merge, uint32_t size,
               uint64_t ordinal)
-      : COFFDefinedFileAtom(file, name, ".bss", scope, typeZeroFill, perms,
-                            ordinal),
+      : COFFDefinedFileAtom(file, name, ".bss", 0, scope, typeZeroFill,
+                            perms, ordinal),
         _merge(merge), _size(size) {}
 
   Merge merge() const override { return _merge; }
diff --git a/lld/lib/ReaderWriter/PECOFF/ReaderCOFF.cpp b/lld/lib/ReaderWriter/PECOFF/ReaderCOFF.cpp
index 8b9e2e8f252..f5ddbe5b832 100644
--- a/lld/lib/ReaderWriter/PECOFF/ReaderCOFF.cpp
+++ b/lld/lib/ReaderWriter/PECOFF/ReaderCOFF.cpp
@@ -694,14 +694,15 @@ std::error_code FileCOFF::AtomizeDefinedSymbolsInSection(
 
   DefinedAtom::ContentType type = getContentType(section);
   DefinedAtom::ContentPermissions perms = getPermissions(section);
+  uint64_t sectionSize = section->SizeOfRawData;
   bool isComdat = (_comdatSections.count(section) == 1);
 
   // Create an atom for the entire section.
   if (symbols.empty()) {
     ArrayRef<uint8_t> data(secData.data(), secData.size());
     auto *atom = new (_alloc) COFFDefinedAtom(
-        *this, "", sectionName, Atom::scopeTranslationUnit, type, isComdat,
-        perms, _merge[section], data, getNextOrdinal());
+        *this, "", sectionName, sectionSize, Atom::scopeTranslationUnit,
+        type, isComdat, perms, _merge[section], data, getNextOrdinal());
     atoms.push_back(atom);
     _definedAtomLocations[section][0].push_back(atom);
     return std::error_code();
@@ -713,8 +714,8 @@ std::error_code FileCOFF::AtomizeDefinedSymbolsInSection(
     uint64_t size = symbols[0].getValue();
     ArrayRef<uint8_t> data(secData.data(), size);
     auto *atom = new (_alloc) COFFDefinedAtom(
-        *this, "", sectionName, Atom::scopeTranslationUnit, type, isComdat,
-        perms, _merge[section], data, getNextOrdinal());
+        *this, "", sectionName, sectionSize, Atom::scopeTranslationUnit,
+        type, isComdat, perms, _merge[section], data, getNextOrdinal());
     atoms.push_back(atom);
     _definedAtomLocations[section][0].push_back(atom);
   }
@@ -726,8 +727,8 @@ std::error_code FileCOFF::AtomizeDefinedSymbolsInSection(
                                         : secData.data() + (si + 1)->getValue();
     ArrayRef<uint8_t> data(start, end);
     auto *atom = new (_alloc) COFFDefinedAtom(
-        *this, _symbolName[*si], sectionName, getScope(*si), type, isComdat,
-        perms, _merge[section], data, getNextOrdinal());
+        *this, _symbolName[*si], sectionName, sectionSize, getScope(*si),
+        type, isComdat, perms, _merge[section], data, getNextOrdinal());
     atoms.push_back(atom);
     _symbolAtom[*si] = atom;
     _definedAtomLocations[section][si->getValue()].push_back(atom);
@@ -982,9 +983,9 @@ std::error_code FileCOFF::maybeCreateSXDataAtoms() {
     return std::error_code();
 
   auto *atom = new (_alloc) COFFDefinedAtom(
-      *this, "", ".sxdata", Atom::scopeTranslationUnit, DefinedAtom::typeData,
-      false /*isComdat*/, DefinedAtom::permR__, DefinedAtom::mergeNo,
-      sxdata, getNextOrdinal());
+      *this, "", ".sxdata", 0, Atom::scopeTranslationUnit,
+      DefinedAtom::typeData, false /*isComdat*/, DefinedAtom::permR__,
+      DefinedAtom::mergeNo, sxdata, getNextOrdinal());
 
   const ulittle32_t *symbolIndex =
       reinterpret_cast<const ulittle32_t *>(sxdata.data());
diff --git a/lld/lib/ReaderWriter/YAML/ReaderWriterYAML.cpp b/lld/lib/ReaderWriter/YAML/ReaderWriterYAML.cpp
index 6f57faee2dc..2d84485a39e 100644
--- a/lld/lib/ReaderWriter/YAML/ReaderWriterYAML.cpp
+++ b/lld/lib/ReaderWriter/YAML/ReaderWriterYAML.cpp
@@ -814,7 +814,8 @@ template <> struct MappingTraits<const lld::DefinedAtom *> {
           _deadStrip(atom->deadStrip()), _dynamicExport(atom->dynamicExport()),
           _codeModel(atom->codeModel()),
           _permissions(atom->permissions()), _size(atom->size()),
-          _sectionName(atom->customSectionName()) {
+          _sectionName(atom->customSectionName()),
+          _sectionSize(atom->sectionSize()) {
       for (const lld::Reference *r : *atom)
         _references.push_back(r);
       if (!atom->occupiesDiskSpace())
@@ -860,6 +861,7 @@ template <> struct MappingTraits<const lld::DefinedAtom *> {
     Alignment alignment() const override { return _alignment; }
     SectionChoice sectionChoice() const override { return _sectionChoice; }
     StringRef customSectionName() const override { return _sectionName; }
+    uint64_t sectionSize() const override { return _sectionSize; }
     SectionPosition sectionPosition() const override { return _sectionPosition; }
     DeadStripKind deadStrip() const override { return _deadStrip; }
     DynamicExport dynamicExport() const override { return _dynamicExport; }
@@ -915,6 +917,7 @@ template <> struct MappingTraits<const lld::DefinedAtom *> {
     std::vector<ImplicitHex8>           _content;
     uint64_t                            _size;
     StringRef                           _sectionName;
+    uint64_t                            _sectionSize;
     std::vector<const lld::Reference *> _references;
     bool _isGroupChild;
   };
@@ -953,6 +956,7 @@ template <> struct MappingTraits<const lld::DefinedAtom *> {
     io.mapOptional("section-name",     keys->_sectionName, StringRef());
     io.mapOptional("section-position", keys->_sectionPosition,
                                          DefinedAtom::sectionPositionAny);
+    io.mapOptional("section-size",     keys->_sectionSize, (uint64_t)0);
     io.mapOptional("dead-strip",       keys->_deadStrip,
                                          DefinedAtom::deadStripNormal);
     io.mapOptional("dynamic-export",   keys->_dynamicExport,
diff --git a/lld/test/pecoff/Inputs/merge-same-size3.obj.yaml b/lld/test/pecoff/Inputs/merge-same-size3.obj.yaml
index a1a8018bcf1..47ad417f2f0 100644
--- a/lld/test/pecoff/Inputs/merge-same-size3.obj.yaml
+++ b/lld/test/pecoff/Inputs/merge-same-size3.obj.yaml
@@ -15,7 +15,7 @@ symbols:
     ComplexType:     IMAGE_SYM_DTYPE_NULL
     StorageClass:    IMAGE_SYM_CLASS_STATIC
     SectionDefinition:
-      Length:          7
+      Length:          2
       NumberOfRelocations: 0
       NumberOfLinenumbers: 0
       CheckSum:        2532800969