[lld-macho] Implement cstring deduplication

[int3]

Summary

Our implementation draws heavily from LLD-ELF's, which in turn delegates
its string deduplication to llvm-mc's StringTableBuilder. The messiness of
this diff is largely due to the fact that we've previously assumed that
all InputSections get concatenated together to form the output. This is
no longer true with CStringInputSections, which split their contents into
StringPieces. StringPieces are much more lightweight than InputSections,
which is important as we create a lot of them. They may also overlap in
the output, which makes it possible for strings to be tail-merged. In
fact, the initial version of this diff implemented tail merging, but
I've dropped it for reasons I'll explain later.

Alignment Issues

Mergeable cstring literals are found under the __TEXT,__cstring
section. In contrast to ELF, which puts strings that need different
alignments into different sections, clang's Mach-O backend puts them all
in one section. Strings that need to be aligned have the .p2align
directive emitted before them, which simply translates into zero padding
in the object file.

I *think* ld64 extracts the desired per-string alignment from this data
by preserving each string's offset from the last section-aligned
address. I'm not entirely certain since it doesn't seem consistent about
doing this; but perhaps this can be chalked up to cases where ld64 has
to deduplicate strings with different offset/alignment combos -- it
seems to pick one of their alignments to preserve. This doesn't seem
correct in general; we can in fact can induce ld64 to produce a crashing
binary just by linking in an additional object file that only contains
cstrings and no code. See PR50563 for details.

Moreover, this scheme seems rather inefficient: since unaligned and
aligned strings are all put in the same section, which has a single
alignment value, it doesn't seem possible to tell whether a given string
doesn't have any alignment requirements. Preserving offset+alignments
for strings that don't need it is wasteful.

In practice, the crashes seen so far seem to stem from x86_64 SIMD
operations on cstrings. X86_64 requires SIMD accesses to be
16-byte-aligned. So for now, I'm thinking of just aligning all strings
to 16 bytes on x86_64. This is indeed wasteful, but implementation-wise
it's simpler than preserving per-string alignment+offsets. It also
avoids the aforementioned crash after deduplication of
differently-aligned strings. Finally, the overhead is not huge: using
16-byte alignment (vs no alignment) is only a 0.5% size overhead when
linking chromium_framework.

With these alignment requirements, it doesn't make sense to attempt tail
merging -- most strings will not be eligible since their overlaps aren't
likely to start at a 16-byte boundary. Tail-merging (with alignment) for
chromium_framework only improves size by 0.3%.

It's worth noting that LLD-ELF only does tail merging at -O2. By
default (at -O1), it just deduplicates w/o tail merging. @thakis has
also mentioned that they saw it regress compressed size in some cases
and therefore turned it off. ld64 does not seem to do tail merging at
all.

Performance Numbers

CString deduplication reduces chromium_framework from 250MB to 242MB, or
about a 3.2% reduction.

Numbers for linking chromium_framework on my 3.2 GHz 16-Core Intel Xeon W:

    N           Min           Max        Median           Avg        Stddev
x  20          3.91          4.03         3.935          3.95   0.034641016
+  20          3.99          4.14         4.015        4.0365     0.0492336
Difference at 95.0% confidence
        0.0865 +/- 0.027245
        2.18987% +/- 0.689746%
        (Student's t, pooled s = 0.0425673)

As expected, cstring merging incurs some non-trivial overhead.

When passing --no-literal-merge, it seems that performance is the
same, i.e. the refactoring in this diff didn't cost us.

    N           Min           Max        Median           Avg        Stddev
x  20          3.91          4.03         3.935          3.95   0.034641016
+  20          3.89          4.02         3.935        3.9435   0.043197831
No difference proven at 95.0% confidence

[int3]

update commit msg

[int3]

remove FIXME

[int3]

remove forward declaration

[int3]

lld/MachO/Writer.cpp

902–903

An earlier implementation of this diff always created the CStringLiteralSection, even if literal merging was disabled. I therefore hoisted out this check to avoid having a conflict between the unneeded CStringLiteralSection and the actual ConcatOutputSection when literal merging was not being done.

We now only create the CStringLiteralSection as-needed, so this is likely unnecessary. However, I think it still makes sense to avoid unnecessary section name conflicts, so I've left it in.

[int3]

[int3]

lld/test/MachO/load-command-sequence.s

33–34 ↗

(On Diff #347173)

while fixing section ordering issues, I noticed that ld64 orders __const after __got, hence this fix.

[gkm]

This comment was removed by gkm.

[int3]

I think the class hierarchy change makes sense as part of this diff, since it's motivated by needs of CStringInputSection's implementation, but yeah I can split out some of the other parts

[int3]

rebase

[thakis]

(FWIW we implemented this in lld-link but then ended up turning it off in chromium since it increased compressed size: https://crbug.com/838449)

[thakis]

(see also D44504)

[int3]

Huh, that makes sense I guess. I suppose we should plan on implementing dedup-without-merge in the future then. Shouldn't be hard to fit into the existing structure.

[int3]

reword error message

[int3]

need to double-check some correctness issues

[int3]

fix alignment issues

[thakis]

A random review might not be the best place for this, but:

1. It's great we're looking at size of the output binary!

2. Maybe it makes sense to look for lower-hanging fruit before implementing somewhat expensive things?

Here's a bloaty (https://github.com/google/bloaty) diff between ld64-linked Chromium Framework (after --, that's where the old version goes) and lld-linked Chromium Framework:

% ~/src/bloaty/bloaty 'Chromium Framework' --  'Chromium.app/Contents/Frameworks/Chromium Framework.framework/Versions/Current/Chromium Framework'
    FILE SIZE        VM SIZE
 --------------  --------------
  [NEW] +6.98Mi  [NEW] +6.98Mi    __DATA_CONST,__const
 +36e2% +6.42Mi +36e2% +6.42Mi    Rebase Info
   +62% +3.19Mi   +62% +3.19Mi    __TEXT,__cstring
  [NEW] +1.52Mi  [NEW] +1.52Mi    __TEXT,__literal16
  +139% +1.11Mi  +139% +1.11Mi    Function Start Addresses
  +1.5%  +940Ki  +1.5%  +940Ki    String Table
 +38e2%  +530Ki +38e2%  +530Ki    __TEXT,__eh_frame
   +27%  +124Ki   +27%  +124Ki    __TEXT,__objc_methtype
  +102%  +118Ki  +102%  +118Ki    __TEXT,__objc_methname
  +1.1%  +114Ki  +1.1%  +114Ki    Symbol Table
  [NEW] +88.0Ki  [NEW] +88.0Ki    __TEXT,__literal8
  +263% +80.9Ki  +263% +80.9Ki    Binding Info
  [NEW] +62.3Ki  [NEW] +62.3Ki    __TEXT,__literal4
  [NEW] +32.4Ki  [NEW] +32.4Ki    __DATA_CONST,__cfstring
  +136% +28.2Ki  +136% +28.2Ki    __DATA,__objc_selrefs
  +0.0% +8.38Ki  -0.0% -6.59Ki    [31 Others]
  [DEL] -26.8Ki  [DEL] -26.8Ki    __DATA,__cfstring
  [DEL] -53.4Ki  [DEL] -53.4Ki    Table of Non-instructions
 -30.7% -57.9Ki -30.7% -57.9Ki    __DATA,__objc_const
  -1.0% -83.3Ki  -1.0% -83.3Ki    __TEXT,__const
  [DEL] -6.98Mi  [DEL] -6.98Mi    __DATA,__const
  +6.0% +14.1Mi  +5.9% +14.1Mi    TOTAL

__cstring is indeed on the list, but there are other things before it. The _DATA_CONST looks like it's just in __DATA in ld64 and just moved around (see 2nd-to-last line), but our rebase info and LC_FUNCTION_STARTS sections are way larger and possibly easier to fix (LC_FUNCTION_STARTS is 2003880 vs 838208 -- that's 1.2 MB that are likely a cheap fix).

3% smaller is great, but 2% slower isn't exactly cheap. It's not super expensive either, but 10% here and 10% there and suddenly you take twice as long. Being much faster is one of the big selling points of lld so we should try hard not to regress on that. Several thoughts on that:

1. Maybe this should be opt in (only at -O2, and/or lto or what)? People who really want optimized binaries over link time probably do (thin) LTO.
2. If the main cost is the hash:
   1. That should parallelize well
   2. Is there some way we could compute the string hash at compile time and stash it somewhere? (Similar in idea to http://blog.llvm.org/2018/01/improving-link-time-on-windows-with.html)

(Some of this also applies to the ICF patch – looks like we're doing a more thorough job than ld64 with ICF but it's also more expensive.)

[int3]

Ah, I should probably have added a bit more motivation. The internal program I've been analyzing has significant size overhead from duplicated CFStrings. These CFStrings are essentially boxed cstrings, with an additional field that needs to be bound by dyld. As such, they bloat not just the __cfstring section but also the binding info. I didn't quantify exactly how much of the binding info could be attributed to them, but it seemed significant.

Ultimately, I think we'll have ICF dedup these CFStrings, but in order to do so we must first dedup the cstrings they point to. Hence this diff.

I'm fine with turning merging off by default for now, until we get it integrated with ICF for a bigger win. And maybe only turn it on together with ICF. How does that sound?

In terms of prioritization, I'd like to keep the implementation of these optimizations simple for now, until we are sure that they are operating correctly. (E.g. as the commit message indicates, I uncovered alignment issues while implementing this, and I'm still not entirely sure this is the best way to handle them.) I think parallelization can wait till we're more certain that the output works...

[int3]

try to fix test on linux

[gkm]

LGTM

lld/MachO/InputSection.h

102

Why are we truncating 64-bit hashes to 32 bits? Because the low-order 32 bits are sufficient, and it's more important that StringPiece be 16 bytes vs. 24 bytes?

lld/MachO/SyntheticSections.cpp

1081–1082

The extremity of the target-dependent difference in alignment requirement is surprising, and worthy of a comment.

lld/test/MachO/cstring-merging.s

55–66

Is there value in testing ...

• Strings of length other than 3?
• Zero length?
• Non-null terminated?
• Prefix matches? (e.g. "foo" and "fool", or "bar" and "barf")

[alexander-shaposhnikov]

lld/MachO/InputSection.h

101

would be good to add comments for these fields (inSecOff, outSecOff)

[alexander-shaposhnikov]

lld/MachO/InputSection.h

76

explicit

124

khm, wouldn't

const StringPiece &getStringPiece(uint64_t offset) const

be a cleaner interface ?

142

does it need to be public ?

[int3]

lld/MachO/InputSection.h

102

This was copied from LLD-ELF's implementation, and yeah the motivation is to reduce the memory cost. I'll copy over the comment too...

142

CStringSection::finalize() needs it to be public

[int3]

address comments + disable literal dedup by default, per @thakis' suggestion

[int3]

lld/MachO/SyntheticSections.cpp

1081–1082

Good point. I've copied the relevant bits of the commit message.

lld/test/MachO/cstring-merging.s

55–66

yeah I got lazy here... those are good suggestions. I don't think prefix matches are necessary since we are no longer doing tail merging, but the rest seem useful.

lld/MachO/ConcatOutputSection.h

 // 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 ConcatOutputSection : public OutputSection {
 public:
   explicit ConcatOutputSection(StringRef name)
       : OutputSection(ConcatKind, name) {}
 
-  const InputSection *firstSection() const { return inputs.front(); }
-  const InputSection *lastSection() const { return inputs.back(); }
+  const ConcatInputSection *firstSection() const { return inputs.front(); }
+  const ConcatInputSection *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 addInput(InputSection *input);
+  void addInput(ConcatInputSection *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;
+  std::vector<ConcatInputSection *> inputs;
+  std::vector<ConcatInputSection *> thunks;
 
   static bool classof(const OutputSection *sec) {
     return sec->kind() == ConcatKind;
   }
 
 private:
   void mergeFlags(InputSection *input);
 
   size_t size = 0;
   uint64_t fileSize = 0;
 };
 
 // We maintain one ThunkInfo per real function.
 //
 // The "active thunk" is represented by the sym/isec pair that
 // turns-over during finalize(): as the call-site address advances,
 // the active thunk goes out of branch-range, and we create a new
 // thunk to take its place.
 //
 // The remaining members -- bools and counters -- apply to the
 // collection of thunks associated with the real function.
 
 struct ThunkInfo {
   // These denote the active thunk:
-  Defined *sym = nullptr;       // private-extern symbol for active thunk
-  InputSection *isec = nullptr; // input section for active thunk
+  Defined *sym = nullptr;             // private-extern symbol for active thunk
+  ConcatInputSection *isec = nullptr; // input section for active thunk
 
   // The following values are cumulative across all thunks on this function
   uint32_t callSiteCount = 0;  // how many calls to the real function?
   uint32_t callSitesUsed = 0;  // how many call sites processed so-far?
   uint32_t thunkCallCount = 0; // how many call sites went to thunk?
   uint8_t sequence = 0;        // how many thunks created so-far?
 };
 
 extern llvm::DenseMap<Symbol *, ThunkInfo> thunkMap;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/ConcatOutputSection.cpp

 
 #include <algorithm>
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace lld;
 using namespace lld::macho;
 
-void ConcatOutputSection::addInput(InputSection *input) {
+void ConcatOutputSection::addInput(ConcatInputSection *input) {
   if (inputs.empty()) {
     align = input->align;
     flags = input->flags;
   } else {
     align = std::max(align, input->align);
     mergeFlags(input);
   }
   inputs.push_back(input);
bool ConcatOutputSection::needsThunks() const {
   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 ConcatOutputSection::estimateStubsInRangeVA(size_t callIdx) const {
   uint64_t branchRange = target->branchRange;
   size_t endIdx = inputs.size();
-  InputSection *isec = inputs[callIdx];
+  ConcatInputSection *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;
   for (auto &tp : thunkMap) {
     ThunkInfo &ti = tp.second;
     maxPotentialThunks +=
log("thunks = " + std::to_string(thunkMap.size()) +
       ", tail = " + to_hexString(isecEnd - isecVA) +
       ", slop = " + to_hexString(branchRange - (isecEnd - isecVA)));
   return stubsInRangeVA;
 }
 
 void ConcatOutputSection::finalize() {
   uint64_t isecAddr = addr;
   uint64_t isecFileOff = fileOff;
-  auto finalizeOne = [&](InputSection *isec) {
+  auto finalizeOne = [&](ConcatInputSection *isec) {
     isecAddr = alignTo(isecAddr, isec->align);
     isecFileOff = alignTo(isecFileOff, isec->align);
     isec->outSecOff = isecAddr - addr;
     isec->outSecFileOff = isecFileOff - fileOff;
     isec->isFinal = true;
     isecAddr += isec->getSize();
     isecFileOff += isec->getFileSize();
   };
 
   if (!needsThunks()) {
-    for (InputSection *isec : inputs)
+    for (ConcatInputSection *isec : inputs)
       finalizeOne(isec);
     size = isecAddr - addr;
     fileSize = isecFileOff - fileOff;
     return;
   }
 
   uint64_t branchRange = target->branchRange;
   uint64_t stubsInRangeVA = TargetInfo::outOfRangeVA;
   size_t thunkSize = target->thunkSize;
   size_t relocCount = 0;
   size_t callSiteCount = 0;
   size_t thunkCallCount = 0;
   size_t thunkCount = 0;
 
   // inputs[finalIdx] is for finalization (address-assignment)
   size_t finalIdx = 0;
   // Kick-off by ensuring that the first input section has an address
   for (size_t callIdx = 0, endIdx = inputs.size(); callIdx < endIdx;
        ++callIdx) {
     if (finalIdx == callIdx)
       finalizeOne(inputs[finalIdx++]);
-    InputSection *isec = inputs[callIdx];
+    ConcatInputSection *isec = inputs[callIdx];
     assert(isec->isFinal);
     uint64_t isecVA = isec->getVA();
     // Assign addresses up-to the forward branch-range limit
     while (finalIdx < endIdx &&
            isecAddr + inputs[finalIdx]->getSize() < isecVA + branchRange)
       finalizeOne(inputs[finalIdx++]);
     if (isec->callSiteCount == 0)
       continue;
for (Reloc &r : reverse(relocs)) {
         // isecAddr and the distance between subsequent call sites is
         // smaller than thunkSize, then a new thunk can go out of
         // range.  Fix by unfinalizing inputs[finalIdx] to reduce the
         // distance between callVA and highVA, then shift some thunks
         // to occupy address-space formerly occupied by the
         // unfinalized inputs[finalIdx].
         fatal(Twine(__FUNCTION__) + ": FIXME: thunk range overrun");
       }
-      thunkInfo.isec = make<InputSection>();
+      thunkInfo.isec = make<ConcatInputSection>();
       thunkInfo.isec->name = isec->name;
       thunkInfo.isec->segname = isec->segname;
       thunkInfo.isec->parent = this;
       StringRef thunkName = saver.save(funcSym->getName() + ".thunk." +
                                        std::to_string(thunkInfo.sequence++));
       r.referent = thunkInfo.sym = symtab->addDefined(
           thunkName, /*file=*/nullptr, thunkInfo.isec, /*value=*/0,
           /*size=*/thunkSize, /*isWeakDef=*/false, /*isPrivateExtern=*/true,

lld/MachO/Config.h

struct Configuration {
   bool searchDylibsFirst = false;
   bool saveTemps = false;
   bool adhocCodesign = false;
   bool emitFunctionStarts = false;
   bool emitBitcodeBundle = false;
   bool emitEncryptionInfo = false;
   bool timeTraceEnabled = false;
   bool dataConst = false;
+  bool mergeLiterals = true;
   uint32_t headerPad;
   uint32_t dylibCompatibilityVersion = 0;
   uint32_t dylibCurrentVersion = 0;
   uint32_t timeTraceGranularity = 500;
   std::string progName;
   llvm::StringRef installName;
   llvm::StringRef mapFile;
   llvm::StringRef outputFile;

lld/MachO/Driver.cpp

 // any CommonSymbols.
 static void replaceCommonSymbols() {
   TimeTraceScope timeScope("Replace common symbols");
   for (Symbol *sym : symtab->getSymbols()) {
     auto *common = dyn_cast<CommonSymbol>(sym);
     if (common == nullptr)
       continue;
 
-    auto *isec = make<InputSection>();
+    auto *isec = make<ConcatInputSection>();
     isec->file = common->getFile();
     isec->name = section_names::common;
     isec->segname = segment_names::data;
     isec->align = common->align;
     // Casting to size_t will truncate large values on 32-bit architectures,
     // but it's not really worth supporting the linking of 64-bit programs on
     // 32-bit archs.
     isec->data = {nullptr, static_cast<size_t>(common->size)};
bool macho::link(ArrayRef<const char *> argsArr, bool canExitEarly,
   config->runtimePaths = args::getStrings(args, OPT_rpath);
   config->allLoad = args.hasArg(OPT_all_load);
   config->forceLoadObjC = args.hasArg(OPT_ObjC);
   config->deadStripDylibs = args.hasArg(OPT_dead_strip_dylibs);
   config->demangle = args.hasArg(OPT_demangle);
   config->implicitDylibs = !args.hasArg(OPT_no_implicit_dylibs);
   config->emitFunctionStarts = !args.hasArg(OPT_no_function_starts);
   config->emitBitcodeBundle = args.hasArg(OPT_bitcode_bundle);
+  config->mergeLiterals = !args.hasArg(OPT_no_literal_merge);
 
   // FIXME: Add a commandline flag for this too.
   config->zeroModTime = getenv("ZERO_AR_DATE");
 
   std::array<PlatformKind, 3> encryptablePlatforms{
       PlatformKind::iOS, PlatformKind::watchOS, PlatformKind::tvOS};
   config->emitEncryptionInfo =
       args.hasFlag(OPT_encryptable, OPT_no_encryption,

lld/MachO/InputFiles.h

 } // namespace MachO
 class TarWriter;
 } // namespace llvm
 
 namespace lld {
 namespace macho {
 
 struct PlatformInfo;
-class InputSection;
+class ConcatInputSection;
 class Symbol;
 struct Reloc;
 enum class RefState : uint8_t;
 
 // If --reproduce option is given, all input files are written
 // to this tar archive.
 extern std::unique_ptr<llvm::TarWriter> tar;
 

 // .o file
 class ObjFile : public InputFile {
 public:
   ObjFile(MemoryBufferRef mb, uint32_t modTime, StringRef archiveName);
   static bool classof(const InputFile *f) { return f->kind() == ObjKind; }
 
   llvm::DWARFUnit *compileUnit = nullptr;
   const uint32_t modTime;
-  std::vector<InputSection *> debugSections;
+  std::vector<ConcatInputSection *> debugSections;
 
 private:
   template <class LP> void parse();
   template <class Section> void parseSections(ArrayRef<Section>);
   template <class LP>
   void parseSymbols(ArrayRef<typename LP::section> sectionHeaders,
                     ArrayRef<typename LP::nlist> nList, const char *strtab,
                     bool subsectionsViaSymbols);

lld/MachO/InputFiles.cpp

 #include "ExportTrie.h"
 #include "InputSection.h"
 #include "MachOStructs.h"
 #include "ObjC.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
+#include "SyntheticSections.h"
 #include "Target.h"
 
 #include "lld/Common/DWARF.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "lld/Common/Reproduce.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/BinaryFormat/MachO.h"
Optional<MemoryBufferRef> macho::readFile(StringRef path) {
   error("unable to find matching architecture in " + path);
   return None;
 }
 
 InputFile::InputFile(Kind kind, const InterfaceFile &interface)
     : id(idCount++), fileKind(kind), name(saver.save(interface.getPath())) {}
 
 template <class Section>
-void ObjFile::parseSections(ArrayRef<Section> sections) {
-  subsections.reserve(sections.size());
-  auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
-
-  for (const Section &sec : sections) {
-    InputSection *isec = make<InputSection>();
-    isec->file = this;
-    isec->name =
-        StringRef(sec.sectname, strnlen(sec.sectname, sizeof(sec.sectname)));
-    isec->segname =
-        StringRef(sec.segname, strnlen(sec.segname, sizeof(sec.segname)));
-    isec->data = {isZeroFill(sec.flags) ? nullptr : buf + sec.offset,
-                  static_cast<size_t>(sec.size)};
-    if (sec.align >= 32)
-      error("alignment " + std::to_string(sec.align) + " of section " +
-            isec->name + " is too large");
-    else
-      isec->align = 1 << sec.align;
-    isec->flags = sec.flags;
+static void parseSection(ObjFile *file, const uint8_t *buf, const Section &sec,
+                         InputSection *isec) {
+  isec->file = file;
+}
+
+template <class Section>
+void ObjFile::parseSections(ArrayRef<Section> sections) {
+  subsections.reserve(sections.size());
+  auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
 
+  for (const Section &sec : sections) {
+    if (config->mergeLiterals && sectionType(sec.flags) == S_CSTRING_LITERALS) {
+      if (sec.nreloc)
+        fatal(toString(this) + " contains relocations in " + sec.segname + "," +
+              sec.sectname +
+              ", so LLD cannot do literal merging. Try re-running with "
+              "--no-literal-merge.");
+
+      auto *isec = make<CStringInputSection>();
+      parseSection(this, buf, sec, isec);
+      isec->splitIntoPieces(); // FIXME: parallelize this?
+      subsections.push_back({{0, isec}});
+    } else {
+      auto *isec = make<ConcatInputSection>();
+      parseSection(this, buf, sec, isec);
       if (!(isDebugSection(isec->flags) &&
             isec->segname == segment_names::dwarf)) {
         subsections.push_back({{0, isec}});
       } else {
         // Instead of emitting DWARF sections, we emit STABS symbols to the
         // object files that contain them. We filter them out early to avoid
         // parsing their relocations unnecessarily. But we must still push an
         // empty map to ensure the indices line up for the remaining sections.
         subsections.push_back({});
         debugSections.push_back(isec);
       }
     }
   }
+}
 
 // Find the subsection corresponding to the greatest section offset that is <=
 // that of the given offset.
 //
 // offset: an offset relative to the start of the original InputSection (before
 // any subsection splitting has occurred). It will be updated to represent the
 // same location as an offset relative to the start of the containing
 // subsection.
for (size_t j = 0; j < symbolIndices.size(); ++j) {
       InputSection *isec = subsecEntry.isec;
 
       uint64_t subsecAddr = sectionAddr + subsecEntry.offset;
       uint64_t symbolOffset = sym.n_value - subsecAddr;
       uint64_t symbolSize =
           j + 1 < symbolIndices.size()
               ? nList[symbolIndices[j + 1]].n_value - sym.n_value
               : isec->data.size() - symbolOffset;
-      // There are 3 cases where we do not need to create a new subsection:
+      // There are 4 cases where we do not need to create a new subsection:
       //   1. If the input file does not use subsections-via-symbols.
       //   2. Multiple symbols at the same address only induce one subsection.
       //      (The symbolOffset == 0 check covers both this case as well as
       //      the first loop iteration.)
       //   3. Alternative entry points do not induce new subsections.
+      //   4. If we have a literal section (e.g. __cstring and __literal4).
       if (!subsectionsViaSymbols || symbolOffset == 0 ||
-          sym.n_desc & N_ALT_ENTRY) {
+          sym.n_desc & N_ALT_ENTRY || !isa<ConcatInputSection>(isec)) {
         symbols[symIndex] =
             createDefined(sym, name, isec, symbolOffset, symbolSize);
         continue;
       }
+      auto *concatIsec = cast<ConcatInputSection>(isec);
 
-      auto *nextIsec = make<InputSection>(*isec);
+      auto *nextIsec = make<ConcatInputSection>(*concatIsec);
       nextIsec->data = isec->data.slice(symbolOffset);
       nextIsec->numRefs = 0;
       nextIsec->wasCoalesced = false;
       isec->data = isec->data.slice(0, symbolOffset);
 
       // By construction, the symbol will be at offset zero in the new
       // subsection.
       symbols[symIndex] =
           createDefined(sym, name, nextIsec, /*value=*/0, symbolSize);
       // TODO: ld64 appears to preserve the original alignment as well as each
       // subsection's offset from the last aligned address. We should consider
       // emulating that behavior.
       nextIsec->align = MinAlign(sectionAlign, sym.n_value);
       subsecMap.push_back({sym.n_value - sectionAddr, nextIsec});
       subsecEntry = subsecMap.back();
     }
   }
 }
 
 OpaqueFile::OpaqueFile(MemoryBufferRef mb, StringRef segName,
                        StringRef sectName)
     : InputFile(OpaqueKind, mb) {
-  InputSection *isec = make<InputSection>();
+  ConcatInputSection *isec = make<ConcatInputSection>();
   isec->file = this;
   isec->name = sectName.take_front(16);
   isec->segname = segName.take_front(16);
   const auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
   isec->data = {buf, mb.getBufferSize()};
   isec->live = true;
   subsections.push_back({{0, isec}});
 }

lld/MachO/InputSection.h

 //===- InputSection.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_INPUT_SECTION_H
 #define LLD_MACHO_INPUT_SECTION_H
 
 #include "Config.h"
 #include "Relocations.h"
 
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/CachedHashString.h"
 #include "llvm/BinaryFormat/MachO.h"
 
 namespace lld {
 namespace macho {
 
 class InputFile;
 class OutputSection;
 
 class InputSection {
 public:
+  enum Kind {
+    ConcatKind,
+    CStringLiteralKind,
+  };
+
+  Kind kind() const { return sectionKind; }
   virtual ~InputSection() = default;
   virtual uint64_t getSize() const { return data.size(); }
   uint64_t getFileSize() const;
-  uint64_t getFileOffset() const;
-  uint64_t getVA() const;
+  // Translates \p off -- an offset relative to this InputSection -- into an
+  // offset from the beginning of its parent OutputSection.
+  virtual uint64_t getOffset(uint64_t off) const = 0;
+  // The offset from the beginning of the file.
+  virtual uint64_t getFileOffset(uint64_t off) const = 0;
+  uint64_t getVA(uint64_t off) const;
 
   void writeTo(uint8_t *buf);
 
   InputFile *file = nullptr;
   StringRef name;
   StringRef segname;
 
   OutputSection *parent = nullptr;
-  uint64_t outSecOff = 0;
-  uint64_t outSecFileOff = 0;
 
   uint32_t align = 1;
   uint32_t flags = 0;
   uint32_t callSiteCount = 0;
   bool isFinal = false; // is address assigned?
 
   // How many symbols refer to this InputSection.
   uint32_t numRefs = 0;
 
   // With subsections_via_symbols, most symbols have their own InputSection,
   // and for weak symbols (e.g. from inline functions), only the
   // InputSection from one translation unit will make it to the output,
   // while all copies in other translation units are coalesced into the
   // first and not copied to the output.
   bool wasCoalesced = false;
 
   bool isCoalescedWeak() const { return wasCoalesced && numRefs == 0; }
   bool shouldOmitFromOutput() const { return !live || isCoalescedWeak(); }
 
   bool live = !config->deadStrip;
 
   ArrayRef<uint8_t> data;
   std::vector<Reloc> relocs;
+
+protected:
+  InputSection(Kind kind) : sectionKind(kind) {}
+
+private:
+  Kind sectionKind;
+};
+
+// ConcatInputSections are combined into (Concat)OutputSections through simple
+// concatentation, in contrast with literal sections which may have their
+// contents merged before output.
+class ConcatInputSection : public InputSection {
+public:
+  ConcatInputSection() : InputSection(ConcatKind) {}
+  uint64_t getFileOffset(uint64_t off) const override;
+  uint64_t getOffset(uint64_t off) const override { return outSecOff + off; }
+  uint64_t getVA() const { return InputSection::getVA(0); }
+
+  static bool classof(const InputSection *isec) {
+    return isec->kind() == ConcatKind;
+  }
+
+  uint64_t outSecOff = 0;
+  uint64_t outSecFileOff = 0;
+};
+
+struct StringPiece {
+  uint32_t inSecOff;
+  uint32_t hash;
+  uint64_t outSecOff;
+
+  StringPiece(uint64_t off, uint32_t hash) : inSecOff(off), hash(hash) {}
+};
+
+// CStringInputSections are composed of multiple null-terminated string
+// literals, which we represent using StringPieces. These literals can be
+// deduplicated and tail-merged, so translating offsets between the input and
+// outputs sections is more complicated.
+//
+// NOTE: One significant difference between LLD and ld64 is that we merge all
+// cstring literals, even those referenced directly by non-private symbols.
+// ld64 is more conservative and does not do that. This was mostly done for
+// implementation simplicity; if we find programs that need the more
+// conservative behavior we can certainly implement that.
+class CStringInputSection : public InputSection {
+public:
+  CStringInputSection() : InputSection(CStringLiteralKind) {}
+  uint64_t getFileOffset(uint64_t off) const override;
+  uint64_t getOffset(uint64_t off) const override;
+  // Find the StringPiece that contains this offset.
+  const StringPiece *getStringPiece(uint64_t off) const;
+  // Split at each null byte.
+  void splitIntoPieces();
+
+  // Returns i'th piece as a CachedHashStringRef. This function is very hot when
+  // string merging is enabled, so we want to inline.
+  LLVM_ATTRIBUTE_ALWAYS_INLINE
+  llvm::CachedHashStringRef getCachedHashStringRef(size_t i) const {
+    size_t begin = pieces[i].inSecOff;
+    size_t end =
+        (pieces.size() - 1 == i) ? data.size() : pieces[i + 1].inSecOff;
+    return {toStringRef(data.slice(begin, end - begin)), pieces[i].hash};
+  }
+
+  static bool classof(const InputSection *isec) {
+    return isec->kind() == CStringLiteralKind;
+  }
+
+  std::vector<StringPiece> pieces;
 };
 
 inline uint8_t sectionType(uint32_t flags) {
   return flags & llvm::MachO::SECTION_TYPE;
 }
 
 inline bool isZeroFill(uint32_t flags) {
   return llvm::MachO::isVirtualSection(sectionType(flags));

 extern std::vector<InputSection *> inputSections;
 
 namespace section_names {
 
 constexpr const char authGot[] = "__auth_got";
 constexpr const char authPtr[] = "__auth_ptr";
 constexpr const char binding[] = "__binding";
 constexpr const char bitcodeBundle[] = "__bundle";
+constexpr const char cString[] = "__cstring";
 constexpr const char cfString[] = "__cfstring";
 constexpr const char codeSignature[] = "__code_signature";
 constexpr const char common[] = "__common";
 constexpr const char compactUnwind[] = "__compact_unwind";
 constexpr const char data[] = "__data";
 constexpr const char debugAbbrev[] = "__debug_abbrev";
 constexpr const char debugInfo[] = "__debug_info";
 constexpr const char debugStr[] = "__debug_str";

lld/MachO/InputSection.cpp

 #include "InputFiles.h"
 #include "OutputSegment.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "Writer.h"
 #include "lld/Common/Memory.h"
 #include "llvm/Support/Endian.h"
+#include "llvm/Support/xxhash.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
 using namespace llvm::support;
 using namespace lld;
 using namespace lld::macho;
 
 std::vector<InputSection *> macho::inputSections;
 
-uint64_t InputSection::getFileOffset() const {
-  return parent->fileOff + outSecFileOff;
+uint64_t ConcatInputSection::getFileOffset(uint64_t off) const {
+  return parent->fileOff + outSecFileOff + off;
 }
 
 uint64_t InputSection::getFileSize() const {
   return isZeroFill(flags) ? 0 : getSize();
 }
 
-uint64_t InputSection::getVA() const { return parent->addr + outSecOff; }
+uint64_t InputSection::getVA(uint64_t off) const {
+  return parent->addr + getOffset(off);
+}
 
 static uint64_t resolveSymbolVA(const Symbol *sym, uint8_t type) {
   const RelocAttrs &relocAttrs = target->getRelocAttrs(type);
   if (relocAttrs.hasAttr(RelocAttrBits::BRANCH))
     return sym->resolveBranchVA();
   else if (relocAttrs.hasAttr(RelocAttrBits::GOT))
     return sym->resolveGotVA();
   else if (relocAttrs.hasAttr(RelocAttrBits::TLV))
for (size_t i = 0; i < relocs.size(); i++) {
     const Reloc &r = relocs[i];
     uint8_t *loc = buf + r.offset;
     uint64_t referentVA = 0;
     if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
       const Symbol *fromSym = r.referent.get<Symbol *>();
       const Reloc &minuend = relocs[++i];
       uint64_t minuendVA;
       if (const Symbol *toSym = minuend.referent.dyn_cast<Symbol *>())
-        minuendVA = toSym->getVA();
+        minuendVA = toSym->getVA() + minuend.addend;
       else {
         auto *referentIsec = minuend.referent.get<InputSection *>();
         assert(!referentIsec->shouldOmitFromOutput());
-        minuendVA = referentIsec->getVA();
+        minuendVA = referentIsec->getVA(minuend.addend);
       }
-      referentVA = minuendVA - fromSym->getVA() + minuend.addend;
+      referentVA = minuendVA - fromSym->getVA();
     } else if (auto *referentSym = r.referent.dyn_cast<Symbol *>()) {
       if (target->hasAttr(r.type, RelocAttrBits::LOAD) &&
           !referentSym->isInGot())
         target->relaxGotLoad(loc, r.type);
-      referentVA = resolveSymbolVA(referentSym, r.type);
+      referentVA = resolveSymbolVA(referentSym, r.type) + r.addend;
 
       if (isThreadLocalVariables(flags)) {
         // References from thread-local variable sections are treated as offsets
         // relative to the start of the thread-local data memory area, which
         // is initialized via copying all the TLV data sections (which are all
         // contiguous).
         if (isa<Defined>(referentSym))
           referentVA -= firstTLVDataSection->addr;
       }
     } else if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
       assert(!referentIsec->shouldOmitFromOutput());
-      referentVA = referentIsec->getVA();
-    }
-    target->relocateOne(loc, r, referentVA + r.addend, getVA() + r.offset);
-  }
+      referentVA = referentIsec->getVA(r.addend);
+    }
+    target->relocateOne(loc, r, referentVA, getVA(r.offset));
+  }
+}
+
+void CStringInputSection::splitIntoPieces() {
+  size_t off = 0;
+  StringRef s = toStringRef(data);
+  while (!s.empty()) {
+    size_t end = s.find(0);
+    if (end == StringRef::npos)
+      fatal(toString(this) + ": string is not null terminated");
+    size_t size = end + 1;
+    pieces.emplace_back(off, xxHash64(s.substr(0, size)));
+    s = s.substr(size);
+    off += size;
+
+const StringPiece *CStringInputSection::getStringPiece(uint64_t off) const {
+  if (off >= data.size())
+    fatal(toString(this) + ": offset is outside the section");
+
+  auto it =
+      partition_point(pieces, [=](StringPiece p) { return p.inSecOff <= off; });
+  return &it[-1];
+}
+
+uint64_t CStringInputSection::getFileOffset(uint64_t off) const {
+  return parent->fileOff + getOffset(off);
+}
+
+uint64_t CStringInputSection::getOffset(uint64_t off) const {
+  const StringPiece &piece = *getStringPiece(off);
+  uint64_t addend = off - piece.inSecOff;
+  return piece.outSecOff + addend;
 }
 
 bool macho::isCodeSection(const InputSection *isec) {
   uint32_t type = isec->flags & SECTION_TYPE;
   if (type != S_REGULAR && type != S_COALESCED)
     return false;
 
   uint32_t attr = isec->flags & SECTION_ATTRIBUTES_USR;

lld/MachO/Options.td

def lto_legacy_pass_manager: Flag<["--"], "lto-legacy-pass-manager">,
     Group<grp_lld>;
 def no_lto_legacy_pass_manager : Flag<["--"], "no-lto-legacy-pass-manager">,
     HelpText<"Use the new pass manager in LLVM">,
     Group<grp_lld>;
 def time_trace: Flag<["--"], "time-trace">, HelpText<"Record time trace">;
 def time_trace_granularity_eq: Joined<["--"], "time-trace-granularity=">,
     HelpText<"Minimum time granularity (in microseconds) traced by time profiler">;
 def time_trace_file_eq: Joined<["--"], "time-trace-file=">, HelpText<"Specify time trace output file">;
+def no_literal_merge: Flag<["--"], "no-literal-merge">, HelpText<"Disable literal merging">;
 
 // This is a complete Options.td compiled from Apple's ld(1) manpage
 // dated 2018-03-07 and cross checked with ld64 source code in repo
 // https://github.com/apple-opensource/ld64 at git tag "512.4" dated
 // 2018-03-18.
 
 // Flags<[HelpHidden]> marks options that are not yet ported to lld,
 // and serve as a scoreboard for annotating our progress toward

lld/MachO/Symbols.cpp

if (!isec->isFinal) {
     assert(target->usesThunks());
 
     // 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;
+  return isec->getVA(value);
 }
 
 uint64_t Defined::getFileOffset() const {
   if (isAbsolute()) {
     error("absolute symbol " + toString(*this) +
           " does not have a file offset");
     return 0;
   }
-  return isec->getFileOffset() + value;
+  return isec->getFileOffset(value);
 }
 
 uint64_t DylibSymbol::getVA() const {
   return isInStubs() ? getStubVA() : Symbol::getVA();
 }
 
 void LazySymbol::fetchArchiveMember() { getFile()->fetch(sym); }

lld/MachO/SyntheticSections.h

 #include "ExportTrie.h"
 #include "InputSection.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "Target.h"
 
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SetVector.h"
+#include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 
 namespace llvm {
 class DWARFUnit;
 } // namespace llvm
 
 namespace lld {

 };
 
 struct Location {
   const InputSection *isec;
   uint64_t offset;
 
   Location(const InputSection *isec, uint64_t offset)
       : isec(isec), offset(offset) {}
-  uint64_t getVA() const { return isec->getVA() + offset; }
+  uint64_t getVA() const { return isec->getVA(offset); }
 };
 
 // Stores rebase opcodes, which tell dyld where absolute addresses have been
 // encoded in the binary. If the binary is not loaded at its preferred address,
 // dyld has to rebase these addresses by adding an offset to them.
 class RebaseSection : public LinkEditSection {
 public:
   RebaseSection();
public:
   DylibSymbol *stubBinder = nullptr;
   Defined *dyldPrivate = nullptr;
 };
 
 // This section contains space for just a single word, and will be used by dyld
 // to cache an address to the image loader it uses. Note that unlike the other
 // synthetic sections, which are OutputSections, the ImageLoaderCacheSection is
 // an InputSection that gets merged into the __data OutputSection.
-class ImageLoaderCacheSection : public InputSection {
+class ImageLoaderCacheSection : public ConcatInputSection {
 public:
   ImageLoaderCacheSection();
   uint64_t getSize() const override { return target->wordSize; }
 };
 
 // Note that this section may also be targeted by non-lazy bindings. In
 // particular, this happens when branch relocations target weak symbols.
 class LazyPointerSection : public SyntheticSection {
public:
   void finalize() override;
   void writeTo(uint8_t *buf) const override;
 
 private:
   llvm::SmallString<261> xarPath;
   uint64_t xarSize;
 };
 
+class CStringSection : public SyntheticSection {
+public:
+  CStringSection();
+  void addInput(CStringInputSection *);
+  uint64_t getSize() const override { return builder.getSize(); }
+  void finalize() override;
+  bool isNeeded() const override { return !inputs.empty(); }
+  void writeTo(uint8_t *buf) const override { builder.write(buf); }
+
+  std::vector<CStringInputSection *> inputs;
+
+private:
+  llvm::StringTableBuilder builder;
+};
+
 struct InStruct {
   MachHeaderSection *header = nullptr;
+  CStringSection *cStringSection = nullptr;
   RebaseSection *rebase = nullptr;
   BindingSection *binding = nullptr;
   WeakBindingSection *weakBinding = nullptr;
   LazyBindingSection *lazyBinding = nullptr;
   ExportSection *exports = nullptr;
   GotSection *got = nullptr;
   TlvPointerSection *tlvPointers = nullptr;
   LazyPointerSection *lazyPointers = nullptr;

lld/MachO/SyntheticSections.cpp

 using namespace lld;
 using namespace lld::macho;
 
 InStruct macho::in;
 std::vector<SyntheticSection *> macho::syntheticSections;
 
 SyntheticSection::SyntheticSection(const char *segname, const char *name)
     : OutputSection(SyntheticKind, name), segname(segname) {
-  isec = make<InputSection>();
+  isec = make<ConcatInputSection>();
   isec->segname = segname;
   isec->name = name;
   isec->parent = this;
-  isec->outSecOff = 0;
   syntheticSections.push_back(this);
 }
 
 // dyld3's MachOLoaded::getSlide() assumes that the __TEXT segment starts
 // from the beginning of the file (i.e. the header).
 MachHeaderSection::MachHeaderSection()
     : SyntheticSection(segment_names::text, section_names::header) {
   // XXX: This is a hack. (See D97007)
if (locations.empty())
     return;
 
   raw_svector_ostream os{contents};
   Rebase lastRebase;
 
   os << static_cast<uint8_t>(REBASE_OPCODE_SET_TYPE_IMM | REBASE_TYPE_POINTER);
 
   llvm::sort(locations, [](const Location &a, const Location &b) {
-    return a.isec->getVA() < b.isec->getVA();
+    return a.isec->getVA(a.offset) < b.isec->getVA(b.offset);
   });
   for (const Location &loc : locations)
-    encodeRebase(loc.isec->parent, loc.isec->outSecOff + loc.offset, lastRebase,
+    encodeRebase(loc.isec->parent, loc.isec->getOffset(loc.offset), lastRebase,
                  os);
   if (lastRebase.consecutiveCount != 0)
     encodeDoRebase(lastRebase, os);
 
   os << static_cast<uint8_t>(REBASE_OPCODE_DONE);
 }
 
 void RebaseSection::writeTo(uint8_t *buf) const {
void BindingSection::finalizeContents() {
   });
   for (const BindingEntry &b : bindings) {
     int16_t ordinal = ordinalForDylibSymbol(*b.dysym);
     if (ordinal != lastBinding.ordinal) {
       encodeDylibOrdinal(ordinal, os);
       lastBinding.ordinal = ordinal;
     }
     encodeBinding(b.dysym, b.target.isec->parent,
-                  b.target.isec->outSecOff + b.target.offset, b.addend,
+                  b.target.isec->getOffset(b.target.offset), b.addend,
                   /*isWeakBinding=*/false, lastBinding, os);
   }
   if (!bindings.empty())
     os << static_cast<uint8_t>(BIND_OPCODE_DONE);
 }
 
 void BindingSection::writeTo(uint8_t *buf) const {
   memcpy(buf, contents.data(), contents.size());
void WeakBindingSection::finalizeContents() {
   // Since bindings are delta-encoded, sorting them allows for a more compact
   // result.
   llvm::sort(bindings,
              [](const WeakBindingEntry &a, const WeakBindingEntry &b) {
                return a.target.getVA() < b.target.getVA();
              });
   for (const WeakBindingEntry &b : bindings)
     encodeBinding(b.symbol, b.target.isec->parent,
-                  b.target.isec->outSecOff + b.target.offset, b.addend,
+                  b.target.isec->getOffset(b.target.offset), b.addend,
                   /*isWeakBinding=*/true, lastBinding, os);
   if (!bindings.empty() || !definitions.empty())
     os << static_cast<uint8_t>(BIND_OPCODE_DONE);
 }
 
 void WeakBindingSection::writeTo(uint8_t *buf) const {
   memcpy(buf, contents.data(), contents.size());
 }
void BitcodeBundleSection::writeTo(uint8_t *buf) const {
   if (ec)
     fatal("failed to map XAR file");
   memcpy(buf, xarMap.const_data(), xarSize);
 
   closeFile(handle);
   remove(xarPath);
 }
 
+CStringSection::CStringSection()
+    : SyntheticSection(segment_names::text, section_names::cString),
+      builder(StringTableBuilder::RAW,
+              /*Alignment=*/target->cpuType == CPU_TYPE_X86_64 ? 16 : 1) {
+  align = target->cpuType == CPU_TYPE_X86_64 ? 16 : 1;
+  flags = S_CSTRING_LITERALS;
+}
+
+void CStringSection::addInput(CStringInputSection *isec) {
+  isec->parent = this;
+  inputs.push_back(isec);
+}
+
+void CStringSection::finalize() {
+  // Add all string pieces to the string table builder to create section
+  // contents.
+  for (const CStringInputSection *isec : inputs)
+    for (size_t i = 0, e = isec->pieces.size(); i != e; ++i)
+      builder.add(isec->getCachedHashStringRef(i));
+
+  // Fix the string table content. After this, the contents will never change.
+  builder.finalizeInOrder();
+
+  // finalize() fixed tail-optimized strings, so we can now get
+  // offsets of strings. Get an offset for each string and save it
+  // to a corresponding SectionPiece for easy access.
+  for (CStringInputSection *isec : inputs) {
+    for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
+      isec->pieces[i].outSecOff =
+          builder.getOffset(isec->getCachedHashStringRef(i));
+      isec->isFinal = true;
+    }
+  }
+}
+
 void macho::createSyntheticSymbols() {
   auto addHeaderSymbol = [](const char *name) {
     symtab->addSynthetic(name, in.header->isec, /*value=*/0,
                          /*privateExtern=*/true, /*includeInSymtab=*/false,
                          /*referencedDynamically=*/false);
   };
 
   switch (config->outputType) {

lld/MachO/UnwindInfoSection.cpp

 // 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(ConcatOutputSection *compactUnwindSection,
                       std::vector<CompactUnwindEntry<Ptr>> &cuVector) {
-  for (const InputSection *isec : compactUnwindSection->inputs) {
+  for (const ConcatInputSection *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());
 
     for (const Reloc &r : isec->relocs) {
       uint64_t referentVA = 0;
       if (auto *referentSym = r.referent.dyn_cast<Symbol *>()) {
         if (!isa<Undefined>(referentSym)) {
           assert(referentSym->isInGot());
           if (auto *defined = dyn_cast<Defined>(referentSym))
             checkTextSegment(defined->isec);
           // At this point in the link, we may not yet know the final address of
           // the GOT, so we just encode the index. We make it a 1-based index so
           // that we can distinguish the null pointer case.
           referentVA = referentSym->gotIndex + 1;
         }
       } else if (auto *referentIsec = r.referent.dyn_cast<InputSection *>()) {
         checkTextSegment(referentIsec);
         if (referentIsec->shouldOmitFromOutput())
           referentVA = UINT64_MAX; // Tombstone value
         else
-          referentVA = referentIsec->getVA() + r.addend;
+          referentVA = referentIsec->getVA(r.addend);
       }
 
       writeAddress(buf + r.offset, referentVA, r.length);
     }
   }
 }
 
 // There should only be a handful of unique personality pointers, so we can

lld/MachO/Writer.cpp

template <class LP> void Writer::createOutputSections() {
   }
 
   // Then add input sections to output sections.
   DenseMap<NamePair, ConcatOutputSection *> concatOutputSections;
   for (const auto &p : enumerate(inputSections)) {
     InputSection *isec = p.value();
     if (isec->shouldOmitFromOutput())
       continue;
+    if (auto *concatIsec = dyn_cast<ConcatInputSection>(isec)) {
       NamePair names = maybeRenameSection({isec->segname, isec->name});
       ConcatOutputSection *&osec = concatOutputSections[names];
       if (osec == nullptr) {
         osec = make<ConcatOutputSection>(names.second);
         osec->inputOrder = p.index();
       }
-    osec->addInput(isec);
+      osec->addInput(concatIsec);
+    } else if (auto *cStringIsec = dyn_cast<CStringInputSection>(isec)) {
+      if (in.cStringSection->inputs.empty())
+        in.cStringSection->inputOrder = p.index();
+      in.cStringSection->addInput(cStringIsec);
+    }
   }
 
+  // Once all the inputs are added, we can finalize the output section
+  // properties and create the corresponding output segments.
   for (const auto &it : concatOutputSections) {
     StringRef segname = it.first.first;
     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 = concatOutputSections.find({ssec->segname, ssec->name});
+    if (ssec->isNeeded()) {
       if (it == concatOutputSections.end()) {
-      if (ssec->isNeeded())
         getOrCreateOutputSegment(ssec->segname)->addOutputSection(ssec);
       } else {
-      error("section from " + toString(it->second->firstSection()->file) +
+        fatal("section from " + toString(it->second->firstSection()->file) +
               " conflicts with synthetic section " + ssec->segname + "," +
               ssec->name);
       }
     }
+  }
 
   // dyld requires __LINKEDIT segment to always exist (even if empty).
   linkEditSegment = getOrCreateOutputSegment(segment_names::linkEdit);
 }
 
 void Writer::finalizeAddresses() {
   TimeTraceScope timeScope("Finalize addresses");
   uint64_t pageSize = target->getPageSize();
template <class LP> void Writer::run() {
   writeMapFile();
   writeOutputFile();
 }
 
 template <class LP> void macho::writeResult() { Writer().run<LP>(); }
 
 void macho::createSyntheticSections() {
   in.header = make<MachHeaderSection>();
+  in.cStringSection = config->mergeLiterals ? make<CStringSection>() : nullptr;
   in.rebase = make<RebaseSection>();
   in.binding = make<BindingSection>();
   in.weakBinding = make<WeakBindingSection>();
   in.lazyBinding = make<LazyBindingSection>();
   in.exports = make<ExportSection>();
   in.got = make<GotSection>();
   in.tlvPointers = make<TlvPointerSection>();
   in.lazyPointers = make<LazyPointerSection>();

lld/test/MachO/cstring-merging.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/more-foo.s -o %t/more-foo.o
+# RUN: %lld -dylib %t/test.o %t/more-foo.o -o %t/test
+# RUN: llvm-objdump --macho --section="__TEXT,__cstring" %t/test | \
+# RUN:   FileCheck %s --check-prefix=STR --implicit-check-not foo --implicit-check-not bar
+# RUN: llvm-objdump --macho --section="__DATA,ptrs" --syms %t/test | FileCheck %s
+# RUN: llvm-readobj --section-headers %t/test | FileCheck %s --check-prefix=HEADER
+
+## Make sure we only have two deduplicated strings in __cstring.
+# STR: Contents of (__TEXT,__cstring) section
+# STR: foo
+# STR: bar
+
+## Make sure both symbol and section relocations point to the right thing.
+# CHECK:      Contents of (__DATA,ptrs) section
+# CHECK-NEXT: __TEXT:__cstring:foo
+# CHECK-NEXT: __TEXT:__cstring:foo
+# CHECK-NEXT: __TEXT:__cstring:foo
+# CHECK-NEXT: __TEXT:__cstring:foo
+# CHECK-NEXT: __TEXT:__cstring:foo
+# CHECK-NEXT: __TEXT:__cstring:foo
+# CHECK-NEXT: __TEXT:__cstring:bar
+
+## Make sure the symbol addresses are correct too.
+# CHECK:     SYMBOL TABLE:
+# CHECK-DAG: [[#%.16x,FOO:]] l     O __TEXT,__cstring _local_foo1
+# CHECK-DAG: [[#FOO]]        l     O __TEXT,__cstring _local_foo2
+# CHECK-DAG: [[#FOO]]        g     O __TEXT,__cstring _globl_foo1
+# CHECK-DAG: [[#FOO]]        g     O __TEXT,__cstring _globl_foo2
+# CHECK-DAG: [[#%.16x,BAR:]] l     O __TEXT,__cstring _bar1
+# CHECK-DAG: [[#BAR]]        l     O __TEXT,__cstring _bar2
+
+## Make sure we set the right alignment and flags.
+# HEADER:        Name: __cstring
+# HEADER-NEXT:   Segment: __TEXT
+# HEADER-NEXT:   Address:
+# HEADER-NEXT:   Size:
+# HEADER-NEXT:   Offset:
+# HEADER-NEXT:   Alignment: 4
+# HEADER-NEXT:   RelocationOffset:
+# HEADER-NEXT:   RelocationCount: 0
+# HEADER-NEXT:   Type: CStringLiterals
+# HEADER-NEXT:   Attributes [ (0x0)
+# HEADER-NEXT:   ]
+# HEADER-NEXT:   Reserved1: 0x0
+# HEADER-NEXT:   Reserved2: 0x0
+# HEADER-NEXT:   Reserved3: 0x0
+
+#--- test.s
+.cstring
+.p2align 2
+_local_foo1:
+  .asciz "foo"
+_local_foo2:
+  .asciz "foo"
+L_.foo1:
+  .asciz "foo"
+L_.foo2:
+  .asciz "foo"
+_bar1:
+  .asciz "bar"
+_bar2:
+  .asciz "bar"
+
+.section __DATA,ptrs,literal_pointers
+.quad L_.foo1
+.quad L_.foo2
+.quad _local_foo1
+.quad _local_foo2
+.quad _globl_foo1
+.quad _globl_foo2
+.quad _bar1
+.quad _bar2
+
+#--- more-foo.s
+.globl _globl_foo1, _globl_foo2
+.cstring
+.p2align 4
+_globl_foo1:
+  .asciz "foo"
+_globl_foo2:
+  .asciz "foo"

lld/test/MachO/invalid/cstring-merging.s

+# REQUIRES: x86
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/not-terminated.s -o %t/not-terminated.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/relocs.s -o %t/relocs.o
+
+# RUN: not %lld -dylib %t/not-terminated.o 2>&1 | FileCheck %s --check-prefix=TERM
+# RUN: not %lld -dylib %t/relocs.o 2>&1 | FileCheck %s --check-prefix=RELOCS
+
+# TERM:   not-terminated.o:(__cstring): string is not null terminated
+# RELOCS: relocs.o contains relocations in __TEXT,__cstring, so LLD cannot do literal merging. Try re-running with --no-literal-merge.
+
+## Make sure things still work reasonably if literal merging is disabled
+# RUN: %lld -dylib --no-literal-merge %t/relocs.o -o %t/relocs
+# RUN: llvm-objdump --macho --syms --full-contents %t/relocs | FileCheck %s
+
+# CHECK: Contents of section __TEXT,__cstring:
+# CHECK: 02d8 666f6f00 d8020000 00000000
+
+# CHECK: SYMBOL TABLE:
+# CHECK: 00000000000002d8 l     O __TEXT,__cstring _str
+
+#--- not-terminated.s
+.cstring
+.asciz "foo"
+.ascii "oh no"
+
+#--- relocs.s
+.cstring
+_str:
+.asciz "foo"
+.quad _str

lld/test/MachO/invalid/reserved-section-name.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
 # RUN: not %lld -o %t %t.o 2>&1 | FileCheck %s -DFILE=%t.o
 # CHECK: error: section from [[FILE]] conflicts with synthetic section __DATA_CONST,__got
 
 .globl _main
 
 .section __DATA_CONST,__got
 .space 1
 
+.data
+_foo:
+.space 1
+
 .text
 _main:
-  mov $0, %rax
+## make sure the GOT will be needed
+  pushq _foo@GOTPCREL(%rip)
   ret

lld/test/MachO/local-got.s

 # RUN: llvm-objdump --macho --full-contents --rebase --bind %t/test | FileCheck %s --check-prefixes=CHECK,PIE --match-full-lines
 # RUN: %lld -no_pie -data_const -lSystem -o %t/test %t/test.o -L%t -lhello
 # RUN: llvm-objdump --macho --full-contents --rebase --bind %t/test | FileCheck %s --check-prefixes=CHECK,NO-PIE --match-full-lines
 
 ## Check that the GOT references the cstrings. --full-contents displays the
 ## address offset and the contents at that address very similarly, so am using
 ## --match-full-lines to make sure we match on the right thing.
 # CHECK:      Contents of section __TEXT,__cstring:
-# CHECK-NEXT: 100000434 {{.*}}
+# CHECK-NEXT: 100000440 {{.*}}
 
 ## 1st 8 bytes refer to the start of __cstring + 0xe, 2nd 8 bytes refer to the
 ## start of __cstring
 # CHECK:      Contents of section __DATA_CONST,__got:
-# CHECK-NEXT: [[#%X,ADDR:]]  42040000 01000000 34040000 01000000 {{.*}}
+# CHECK-NEXT: [[#%X,ADDR:]]  50040000 01000000 40040000 01000000 {{.*}}
 # CHECK-NEXT: [[#ADDR + 16]] 00000000 00000000 {{.*}}
 
 ## Check that the rebase table is empty.
 # NO-PIE:      Rebase table:
 # NO-PIE-NEXT: segment      section  address         type
 
 # PIE:      Rebase table:
 # PIE-NEXT: segment      section  address          type

lld/test/MachO/section-headers.s

 # CHECK-NEXT: Attributes [ (0x800004)
 # CHECK-NEXT:   PureInstructions (0x800000)
 # CHECK-NEXT:   SomeInstructions (0x4)
 # CHECK-NEXT: ]
 
 # CHECK:      Name: __cstring
 # CHECK-NEXT: Segment: __TEXT
 # CHECK-NOT:  }
-# CHECK:      Alignment: 2
+# CHECK:      Alignment: 4
 # CHECK-NOT:  }
 # CHECK:      Type: CStringLiterals (0x2)
 # CHECK-NEXT: Attributes [ (0x0)
 # CHECK-NEXT: ]
 
 # CHECK:      Name: maxlen_16ch_name
 # CHECK-NEXT: Segment: __TEXT
 # CHECK-NEXT: Address:

lld/test/MachO/subsections-section-relocs.s

 # REQUIRES: x86
 # RUN: rm -rf %t; split-file %s %t
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/test.s -o %t/test.o
 
-# RUN: %lld -o %t/test %t/test.o -order_file %t/order-file
+# RUN: %lld --no-literal-merge -o %t/test %t/test.o -order_file %t/order-file
 # RUN: llvm-objdump --section-headers -d --no-show-raw-insn %t/test | FileCheck %s
 # CHECK-LABEL: Sections:
 # CHECK:       __cstring {{[^ ]*}} {{0*}}[[#%x, CSTRING_ADDR:]]
 # CHECK-LABEL: Disassembly of section __TEXT,__text:
 ## L._str should end up at CSTRING_ADDR + 4, and leaq is 7 bytes long so we
 ## have RIP = ADDR + 7
 # CHECK:       [[#%x, ADDR:]]: leaq
 # CHECK-SAME:    [[#%u, CSTRING_ADDR + 4 - ADDR - 7]](%rip), %rsi {{.*}} <_bar_str+0x4>

 _foo_str:
   .asciz "foo"
 
 _bar_str:
   .asciz "bar"
 
 ## References to this generate a section relocation
 ## N.B.: ld64 doesn't actually reorder symbols in __cstring based on the order
-##       file. Only our implementation does. However, I'm not sure how else to
-##       test section relocations that target an address inside a relocated
-##       symbol: using a non-__cstring section would cause llvm-mc to emit a
-##       symbol relocation instead using the nearest symbol.
+##       file. Our implementation only does does so if --no-literal-merge is
+##       specified. I'm not sure how else to test section relocations that
+##       target an address inside a relocated symbol: using a non-__cstring
+##       section would cause llvm-mc to emit a symbol relocation instead using
+##       the nearest symbol. It might be more consistent for LLD to disable
+##       symbol-based cstring reordering altogether and leave this functionality
+##       untested, at least until we find a real-world use case...
 L_.str:
   .asciz "Private symbol"
 
 .subsections_via_symbols

lld/test/MachO/x86-64-relocs.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
 # RUN: %lld -lSystem -o %t %t.o
 # RUN: llvm-objdump --section-headers --syms -d %t | FileCheck %s
 
 # CHECK-LABEL: Sections:
-# CHECK:       __cstring {{[0-9a-z]+}} [[#%x, CSTRING_ADDR:]]
+# CHECK:       __data {{[0-9a-z]+}} [[#%x, DATA_ADDR:]]
 
 # CHECK-LABEL: SYMBOL TABLE:
 # CHECK:       [[#%x, F_ADDR:]] {{.*}} _f
 
 # CHECK-LABEL: <_main>:
 ## Test X86_64_RELOC_BRANCH
 # CHECK:       callq 0x[[#%x, F_ADDR]] <_f>
 ## Test extern (symbol) X86_64_RELOC_SIGNED
-# CHECK:       leaq [[#%u, STR_OFF:]](%rip), %rsi
-# CHECK-NEXT:  [[#%x, CSTRING_ADDR - STR_OFF]]
+# CHECK:       leaq [[#%u, LOCAL_OFF:]](%rip), %rsi
+# CHECK-NEXT:  [[#%x, DATA_ADDR - LOCAL_OFF]]
 ## Test non-extern (section) X86_64_RELOC_SIGNED
-# CHECK:       leaq [[#%u, LSTR_OFF:]](%rip), %rsi
-# CHECK-NEXT:  [[#%x, CSTRING_ADDR + 22 - LSTR_OFF]]
+# CHECK:       leaq [[#%u, PRIVATE_OFF:]](%rip), %rsi
+# CHECK-NEXT:  [[#%x, DATA_ADDR + 8 - PRIVATE_OFF]]
 
 # RUN: llvm-objdump --section=__const --full-contents %t | FileCheck %s --check-prefix=NONPCREL
 # NONPCREL:      Contents of section __DATA_CONST,__const:
-# NONPCREL-NEXT: 100001000 18040000 01000000 18040000 01000000
+# NONPCREL-NEXT: 100001000 08200000 01000000 08200000 01000000
 
 .section __TEXT,__text
 .globl _main, _f
 _main:
   callq _f # X86_64_RELOC_BRANCH
   mov $0, %rax
   ret
 
 _f:
-  movl $0x2000004, %eax # write() syscall
-  mov $1, %rdi # stdout
-  leaq _str(%rip), %rsi # Generates a X86_64_RELOC_SIGNED pcrel symbol relocation
-  mov $21, %rdx # length of str
-  syscall
-
-  movl $0x2000004, %eax # write() syscall
-  mov $1, %rdi # stdout
-  leaq L_.str(%rip), %rsi # Generates a X86_64_RELOC_SIGNED pcrel section relocation
-  mov $15, %rdx # length of str
-  syscall
-
-  movl $0x2000004, %eax # write() syscall
-  mov $1, %rdi # stdout
-  movq L_.ptr_1_to_str(%rip), %rsi
-  mov $15, %rdx # length of str
-  syscall
+  leaq _local(%rip), %rsi # Generates a X86_64_RELOC_SIGNED pcrel symbol relocation
+  leaq L_.private(%rip), %rsi # Generates a X86_64_RELOC_SIGNED pcrel section relocation
+  movq L_.ptr_1(%rip), %rsi
   ret
 
-.section __TEXT,__cstring
+.data
 ## References to this generate a symbol relocation
-_str:
-  .asciz "Local defined symbol\n"
+_local:
+  .quad 123
 ## References to this generate a section relocation
-L_.str:
-  .asciz "Private symbol\n"
+L_.private:
+  .quad 123
 
 .section __DATA,__const
 ## These generate X86_64_RELOC_UNSIGNED non-pcrel section relocations
-L_.ptr_1_to_str:
-  .quad L_.str
-L_.ptr_2_to_str:
-  .quad L_.str
+L_.ptr_1:
+  .quad L_.private
+L_.ptr_2:
+  .quad L_.private