[lld-macho][nfc] Rename MergedOutputSection to ConcatOutputSection

[int3]

Summary

The ELF format has the concept of merge sections (marked by SHF_MERGE),
which contain data that can be safely deduplicated. The Mach-O
equivalents are called literal sections (marked by S_CSTRING_LITERALS or
S_{4,8,16}BYTE_LITERALS). While the Mach-O format doesn't use the word
'merge', to avoid confusion, I've renamed our MergedOutputSection to
ConcatOutputSection. I believe it's a more descriptive name too.

This renaming sets the stage for D102964: [lld-macho] Implement cstring deduplication.

[alexander-shaposhnikov]

lld/MachO/ConcatOutputSection.h

29–30

explicit

[int3]

[gkm]

lld/MachO/ConcatOutputSection.h

30

s/MergedKind/ConcatKind/

lld/MachO/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS Options.td)
 tablegen(LLVM Options.inc -gen-opt-parser-defs)
 add_public_tablegen_target(MachOOptionsTableGen)
 
 include_directories(${LLVM_MAIN_SRC_DIR}/../libunwind/include)
 
 add_lld_library(lldMachO2
   Arch/ARM.cpp
   Arch/ARM64.cpp
   Arch/ARM64Common.cpp
   Arch/ARM64_32.cpp
   Arch/X86_64.cpp
-  UnwindInfoSection.cpp
+  ConcatOutputSection.cpp
   Driver.cpp
   DriverUtils.cpp
   Dwarf.cpp
   ExportTrie.cpp
   InputFiles.cpp
   InputSection.cpp
   LTO.cpp
-  MergedOutputSection.cpp
+  MapFile.cpp
   ObjC.cpp
   OutputSection.cpp
   OutputSegment.cpp
   Relocations.cpp
   SymbolTable.cpp
   Symbols.cpp
   SyntheticSections.cpp
   Target.cpp
-  MapFile.cpp
+  UnwindInfoSection.cpp
   Writer.cpp
 
   LINK_COMPONENTS
   ${LLVM_TARGETS_TO_BUILD}
   BinaryFormat
   BitReader
   Core
   DebugInfoDWARF

lld/MachO/ConcatOutputSection.h

-//===- OutputSection.h ------------------------------------------*- C++ -*-===//
+//===- ConcatOutputSection.h ------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_MERGED_OUTPUT_SECTION_H

 namespace macho {
 
 class Defined;
 
 // Linking multiple files will inevitably mean resolving sections in different
 // files that are labeled with the same segment and section name. This class
 // contains all such sections and writes the data from each section sequentially
 // in the final binary.
-class MergedOutputSection : public OutputSection {
+class ConcatOutputSection : public OutputSection {
 public:
-  MergedOutputSection(StringRef name) : OutputSection(MergedKind, name) {}
+  explicit ConcatOutputSection(StringRef name)
+      : OutputSection(ConcatKind, name) {}
 
   const InputSection *firstSection() const { return inputs.front(); }
   const InputSection *lastSection() const { return inputs.back(); }
 
   // These accessors will only be valid after finalizing the section
   uint64_t getSize() const override { return size; }
   uint64_t getFileSize() const override { return fileSize; }
 
-  void mergeInput(InputSection *input);
+  void addInput(InputSection *input);
   void finalize() override;
   bool needsThunks() const;
   uint64_t estimateStubsInRangeVA(size_t callIdx) const;
 
   void writeTo(uint8_t *buf) const override;
 
   std::vector<InputSection *> inputs;
   std::vector<InputSection *> thunks;
 
   static bool classof(const OutputSection *sec) {
-    return sec->kind() == MergedKind;
+    return sec->kind() == ConcatKind;
   }
 
 private:
   void mergeFlags(InputSection *input);
 
   size_t size = 0;
   uint64_t fileSize = 0;
 };

lld/MachO/ConcatOutputSection.cpp

-//===- OutputSection.cpp --------------------------------------------------===//
+//===- ConcatOutputSection.cpp --------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
-#include "MergedOutputSection.h"
+#include "ConcatOutputSection.h"
 #include "Config.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/MachO.h"
 #include "llvm/Support/ScopedPrinter.h"
 
 #include <algorithm>
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace lld;
 using namespace lld::macho;
 
-void MergedOutputSection::mergeInput(InputSection *input) {
+void ConcatOutputSection::addInput(InputSection *input) {
   if (inputs.empty()) {
     align = input->align;
     flags = input->flags;
   } else {
     align = std::max(align, input->align);
     mergeFlags(input);
   }
   inputs.push_back(input);

 
 DenseMap<Symbol *, ThunkInfo> lld::macho::thunkMap;
 
 // Determine whether we need thunks, which depends on the target arch -- RISC
 // (i.e., ARM) generally does because it has limited-range branch/call
 // instructions, whereas CISC (i.e., x86) generally doesn't. RISC only needs
 // thunks for programs so large that branch source & destination addresses
 // might differ more than the range of branch instruction(s).
-bool MergedOutputSection::needsThunks() const {
+bool ConcatOutputSection::needsThunks() const {
   if (!target->usesThunks())
     return false;
   uint64_t isecAddr = addr;
   for (InputSection *isec : inputs)
     isecAddr = alignTo(isecAddr, isec->align) + isec->getSize();
   if (isecAddr - addr + in.stubs->getSize() <= target->branchRange)
     return false;
   // Yes, this program is large enough to need thunks.
   for (InputSection *isec : inputs) {
     for (Reloc &r : isec->relocs) {
       if (!target->hasAttr(r.type, RelocAttrBits::BRANCH))
         continue;
       auto *sym = r.referent.get<Symbol *>();
       // Pre-populate the thunkMap and memoize call site counts for every
       // InputSection and ThunkInfo. We do this for the benefit of
-      // MergedOutputSection::estimateStubsInRangeVA()
+      // ConcatOutputSection::estimateStubsInRangeVA()
       ThunkInfo &thunkInfo = thunkMap[sym];
       // Knowing ThunkInfo call site count will help us know whether or not we
       // might need to create more for this referent at the time we are
       // estimating distance to __stubs in .
       ++thunkInfo.callSiteCount;
       // Knowing InputSection call site count will help us avoid work on those
       // that have no BRANCH relocs.
       ++isec->callSiteCount;
     }
   }
   return true;
 }
 
 // Since __stubs is placed after __text, we must estimate the address
 // beyond which stubs are within range of a simple forward branch.
-uint64_t MergedOutputSection::estimateStubsInRangeVA(size_t callIdx) const {
+uint64_t ConcatOutputSection::estimateStubsInRangeVA(size_t callIdx) const {
   uint64_t branchRange = target->branchRange;
   size_t endIdx = inputs.size();
   InputSection *isec = inputs[callIdx];
   uint64_t isecVA = isec->getVA();
   // Tally the non-stub functions which still have call sites
   // remaining to process, which yields the maximum number
   // of thunks we might yet place.
   size_t maxPotentialThunks = 0;
log("thunks = " + std::to_string(thunkMap.size()) +
       ", stubs = " + std::to_string(in.stubs->getSize()) + ", isecVA = " +
       to_hexString(isecVA) + ", threshold = " + to_hexString(stubsInRangeVA) +
       ", isecEnd = " + to_hexString(isecEnd) +
       ", tail = " + to_hexString(isecEnd - isecVA) +
       ", slop = " + to_hexString(branchRange - (isecEnd - isecVA)));
   return stubsInRangeVA;
 }
 
-void MergedOutputSection::finalize() {
+void ConcatOutputSection::finalize() {
   uint64_t isecAddr = addr;
   uint64_t isecFileOff = fileOff;
   auto finalizeOne = [&](InputSection *isec) {
     isecAddr = alignTo(isecAddr, isec->align);
     isecFileOff = alignTo(isecFileOff, isec->align);
     isec->outSecOff = isecAddr - addr;
     isec->outSecFileOff = isecFileOff - fileOff;
     isec->isFinal = true;
void ConcatOutputSection::finalize() {
   log("thunks for " + parent->name + "," + name +
       ": funcs = " + std::to_string(thunkMap.size()) +
       ", relocs = " + std::to_string(relocCount) +
       ", all calls = " + std::to_string(callSiteCount) +
       ", thunk calls = " + std::to_string(thunkCallCount) +
       ", thunks = " + std::to_string(thunkCount));
 }
 
-void MergedOutputSection::writeTo(uint8_t *buf) const {
+void ConcatOutputSection::writeTo(uint8_t *buf) const {
   // Merge input sections from thunk & ordinary vectors
   size_t i = 0, ie = inputs.size();
   size_t t = 0, te = thunks.size();
   while (i < ie || t < te) {
     while (i < ie && (t == te || inputs[i]->getSize() == 0 ||
                       inputs[i]->outSecOff < thunks[t]->outSecOff)) {
       inputs[i]->writeTo(buf + inputs[i]->outSecFileOff);
       ++i;
     }
     while (t < te && (i == ie || thunks[t]->outSecOff < inputs[i]->outSecOff)) {
       thunks[t]->writeTo(buf + thunks[t]->outSecFileOff);
       ++t;
     }
   }
 }
 
 // TODO: this is most likely wrong; reconsider how section flags
 // are actually merged. The logic presented here was written without
 // any form of informed research.
-void MergedOutputSection::mergeFlags(InputSection *input) {
+void ConcatOutputSection::mergeFlags(InputSection *input) {
   uint8_t baseType = flags & SECTION_TYPE;
   uint8_t inputType = input->flags & SECTION_TYPE;
   if (baseType != inputType)
     error("Cannot merge section " + input->name + " (type=0x" +
           to_hexString(inputType) + ") into " + name + " (type=0x" +
           to_hexString(baseType) + "): inconsistent types");
 
   constexpr uint32_t strictFlags = S_ATTR_DEBUG | S_ATTR_STRIP_STATIC_SYMS |

lld/MachO/OutputSection.h

 
 // Output sections represent the finalized sections present within the final
 // linked executable. They can represent special sections (like the symbol
 // table), or represent coalesced sections from the various inputs given to the
 // linker with the same segment / section name.
 class OutputSection {
 public:
   enum Kind {
-    MergedKind,
+    ConcatKind,
     SyntheticKind,
   };
 
   OutputSection(Kind kind, StringRef name) : name(name), sectionKind(kind) {}
   virtual ~OutputSection() = default;
   Kind kind() const { return sectionKind; }
 
   // These accessors will only be valid after finalizing the section.

lld/MachO/OutputSegment.cpp

 //===- OutputSegment.cpp --------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "OutputSegment.h"
+#include "ConcatOutputSection.h"
 #include "InputSection.h"
-#include "MergedOutputSection.h"
 #include "SyntheticSections.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/MachO.h"
 
 using namespace llvm;
 using namespace llvm::MachO;

lld/MachO/Symbols.cpp

uint64_t Defined::getVA() const {
   if (isAbsolute())
     return value;
 
   if (!isec->isFinal) {
     // A target arch that does not use thunks ought never ask for
     // the address of a function that has not yet been finalized.
     assert(target->usesThunks());
 
-    // MergedOutputSection::finalize() can seek the address of a
+    // ConcatOutputSection::finalize() can seek the address of a
     // function before its address is assigned. The thunking algorithm
     // knows that unfinalized functions will be out of range, so it is
     // expedient to return a contrived out-of-range address.
     return TargetInfo::outOfRangeVA;
   }
   return isec->getVA() + value;
 }
 

lld/MachO/SyntheticSections.h

public:
   bool isNeeded() const override { return !entries.empty(); }
   void finalize() override;
   void writeTo(uint8_t *buf) const override;
   const llvm::SetVector<Symbol *> &getEntries() const { return entries; }
   // Returns whether the symbol was added. Note that every stubs entry will
   // have a corresponding entry in the LazyPointerSection.
   bool addEntry(Symbol *);
   uint64_t getVA(uint32_t stubsIndex) const {
-    // MergedOutputSection::finalize() can seek the address of a
+    // ConcatOutputSection::finalize() can seek the address of a
     // stub before its address is assigned. Before __stubs is
     // finalized, return a contrived out-of-range address.
     return isFinal ? addr + stubsIndex * target->stubSize
                    : TargetInfo::outOfRangeVA;
   }
 
   bool isFinal = false; // is address assigned?
 

lld/MachO/SyntheticSections.cpp

 //===- SyntheticSections.cpp ---------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "SyntheticSections.h"
+#include "ConcatOutputSection.h"
 #include "Config.h"
 #include "ExportTrie.h"
 #include "InputFiles.h"
 #include "MachOStructs.h"
-#include "MergedOutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Writer.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/ADT/STLExtras.h"

lld/MachO/UnwindInfoSection.h

 //===- UnwindInfoSection.h ------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_UNWIND_INFO_H
 #define LLD_MACHO_UNWIND_INFO_H
 
-#include "MergedOutputSection.h"
+#include "ConcatOutputSection.h"
 #include "SyntheticSections.h"
 
 #include "mach-o/compact_unwind_encoding.h"
 #include "llvm/ADT/DenseMap.h"
 
 #include <vector>
 
 namespace lld {
 namespace macho {
 
 class UnwindInfoSection : public SyntheticSection {
 public:
   bool isNeeded() const override { return compactUnwindSection != nullptr; }
   uint64_t getSize() const override { return unwindInfoSize; }
   virtual void prepareRelocations(InputSection *) = 0;
 
-  void setCompactUnwindSection(MergedOutputSection *cuSection) {
+  void setCompactUnwindSection(ConcatOutputSection *cuSection) {
     compactUnwindSection = cuSection;
   }
 
 protected:
   UnwindInfoSection()
       : SyntheticSection(segment_names::text, section_names::unwindInfo) {
     align = 4;
   }
 
-  MergedOutputSection *compactUnwindSection = nullptr;
+  ConcatOutputSection *compactUnwindSection = nullptr;
   uint64_t unwindInfoSize = 0;
 };
 
 UnwindInfoSection *makeUnwindInfoSection();
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/UnwindInfoSection.cpp

 //===- UnwindInfoSection.cpp ----------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "UnwindInfoSection.h"
+#include "ConcatOutputSection.h"
 #include "Config.h"
 #include "InputSection.h"
-#include "MergedOutputSection.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"

 }
 
 // We need to apply the relocations to the pre-link compact unwind section
 // before converting it to post-link form. There should only be absolute
 // relocations here: since we are not emitting the pre-link CU section, there
 // is no source address to make a relative location meaningful.
 template <class Ptr>
 static void
-relocateCompactUnwind(MergedOutputSection *compactUnwindSection,
+relocateCompactUnwind(ConcatOutputSection *compactUnwindSection,
                       std::vector<CompactUnwindEntry<Ptr>> &cuVector) {
   for (const InputSection *isec : compactUnwindSection->inputs) {
     assert(isec->parent == compactUnwindSection);
 
     uint8_t *buf =
         reinterpret_cast<uint8_t *>(cuVector.data()) + isec->outSecFileOff;
     memcpy(buf, isec->data.data(), isec->data.size());
 

lld/MachO/Writer.cpp

 //===- Writer.cpp ---------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "Writer.h"
+#include "ConcatOutputSection.h"
 #include "Config.h"
 #include "InputFiles.h"
 #include "InputSection.h"
 #include "MapFile.h"
-#include "MergedOutputSection.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "UnwindInfoSection.h"
 
for (OutputSection *osec : seg->getSections()) {
       // Now that the output sections are sorted, assign the final
       // output section indices.
       if (!osec->isHidden())
         osec->index = ++sectionIndex;
       if (!firstTLVDataSection && isThreadLocalData(osec->flags))
         firstTLVDataSection = osec;
 
       if (!isecPriorities.empty()) {
-        if (auto *merged = dyn_cast<MergedOutputSection>(osec)) {
+        if (auto *merged = dyn_cast<ConcatOutputSection>(osec)) {
           llvm::stable_sort(merged->inputs,
                             [&](InputSection *a, InputSection *b) {
                               return isecPriorities[a] > isecPriorities[b];
                             });
         }
       }
     }
   }
case MH_EXECUTE:
     break;
   case MH_DYLIB:
   case MH_BUNDLE:
     break;
   default:
     llvm_unreachable("unhandled output file type");
   }
 
-  // Then merge input sections into output sections.
-  MapVector<NamePair, MergedOutputSection *> mergedOutputSections;
+  // Then add input sections to output sections.
+  MapVector<NamePair, ConcatOutputSection *> concatOutputSections;
   for (InputSection *isec : inputSections) {
     if (isec->shouldOmitFromOutput())
       continue;
     NamePair names = maybeRenameSection({isec->segname, isec->name});
-    MergedOutputSection *&osec = mergedOutputSections[names];
+    ConcatOutputSection *&osec = concatOutputSections[names];
     if (osec == nullptr)
-      osec = make<MergedOutputSection>(names.second);
-    osec->mergeInput(isec);
+      osec = make<ConcatOutputSection>(names.second);
+    osec->addInput(isec);
   }
 
-  for (const auto &it : mergedOutputSections) {
+  for (const auto &it : concatOutputSections) {
     StringRef segname = it.first.first;
-    MergedOutputSection *osec = it.second;
+    ConcatOutputSection *osec = it.second;
     if (segname == segment_names::ld) {
       assert(osec->name == section_names::compactUnwind);
       in.unwindInfo->setCompactUnwindSection(osec);
     } else {
       getOrCreateOutputSegment(segname)->addOutputSection(osec);
     }
   }
 
   for (SyntheticSection *ssec : syntheticSections) {
-    auto it = mergedOutputSections.find({ssec->segname, ssec->name});
-    if (it == mergedOutputSections.end()) {
+    auto it = concatOutputSections.find({ssec->segname, ssec->name});
+    if (it == concatOutputSections.end()) {
       if (ssec->isNeeded())
         getOrCreateOutputSegment(ssec->segname)->addOutputSection(ssec);
     } else {
       error("section from " + toString(it->second->firstSection()->file) +
             " conflicts with synthetic section " + ssec->segname + "," +
             ssec->name);
     }
   }