[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

936–937

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

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

101

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

1072–1073

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

100

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

[alexander-shaposhnikov]

lld/MachO/InputSection.h

75

explicit

123

khm, wouldn't

const StringPiece &getStringPiece(uint64_t offset) const

be a cleaner interface ?

141

does it need to be public ?

[int3]

lld/MachO/InputSection.h

101

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...

141

CStringSection::finalize() needs it to be public

[int3]

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

[int3]

lld/MachO/SyntheticSections.cpp

1072–1073

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/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
   ObjC.cpp
   OutputSection.cpp
   OutputSegment.cpp
   Relocations.cpp
   SymbolTable.cpp
   Symbols.cpp
   SyntheticSections.cpp
   Target.cpp

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) {}
+  ConcatOutputSection(StringRef name) : OutputSection(MergedKind, 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 mergeInput(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() == MergedKind;
   }
 
 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

-//===- 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(ConcatInputSection *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];
+  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()) +
       ", 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) {
+  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,
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/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)};
config->ltoNewPassManager =
                    LLVM_ENABLE_NEW_PASS_MANAGER);
   config->runtimePaths = args::getStrings(args, OPT_rpath);
   config->allLoad = args.hasArg(OPT_all_load);
   config->forceLoadObjC = args.hasArg(OPT_ObjC);
   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);
 
   std::array<PlatformKind, 3> encryptablePlatforms{
       PlatformKind::iOS, PlatformKind::watchOS, PlatformKind::tvOS};
   config->emitEncryptionInfo =
       args.hasFlag(OPT_encryptable, OPT_no_encryption,
                    is_contained(encryptablePlatforms, config->platform()));
 
 #ifndef HAVE_LIBXAR

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 a cstring_literals section, so LLD "
+              "cannot do string 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->canOmitFromOutput = 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()};
   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 "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;
 
   // True if this InputSection could not be written to the output file.
   // With subsections_via_symbols, most symbol have its 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 canOmitFromOutput = false;
 
   bool shouldOmitFromOutput() const {
     return canOmitFromOutput && numRefs == 0;
   }
 
   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/OutputSection.h

virtual void finalize() {
     // TODO investigate refactoring synthetic section finalization logic into
     // overrides of this function.
   }
 
   virtual void writeTo(uint8_t *buf) const = 0;
 
   StringRef name;
   OutputSegment *parent = nullptr;
+  // For output sections that don't have explicit ordering requirements, their
+  // output order should be based on the relative ordering of the input sections
+  // they contain.
+  size_t inputOrder = 0;
 
   uint32_t index = 0;
   uint64_t addr = 0;
   uint64_t fileOff = 0;
   uint32_t align = 1;
   uint32_t flags = 0;
   uint32_t reserved1 = 0;
   uint32_t reserved2 = 0;

lld/MachO/OutputSegment.h

 class OutputSegment {
 public:
   const OutputSection *firstSection() const { return sections.front(); }
   const OutputSection *lastSection() const { return sections.back(); }
 
   void addOutputSection(OutputSection *os);
   void sortOutputSections(
       llvm::function_ref<bool(OutputSection *, OutputSection *)> comparator) {
-    llvm::stable_sort(sections, comparator);
+    llvm::sort(sections, comparator);
   }
 
   const std::vector<OutputSection *> &getSections() const { return sections; }
   size_t numNonHiddenSections() const;
 
   uint64_t fileOff = 0;
   uint64_t fileSize = 0;
   uint64_t vmSize = 0;
+  size_t inputOrder = 0;
   StringRef name;
   uint32_t maxProt = 0;
   uint32_t initProt = 0;
   uint8_t index;
 
 private:
   std::vector<OutputSection *> sections;
 };

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;

 size_t OutputSegment::numNonHiddenSections() const {
   size_t count = 0;
   for (const OutputSection *osec : sections)
     count += (!osec->isHidden() ? 1 : 0);
   return count;
 }
 
 void OutputSegment::addOutputSection(OutputSection *osec) {
+  if (sections.empty())
+    inputOrder = osec->inputOrder;
+
   osec->parent = this;
   sections.push_back(osec);
 
   for (const SectionAlign &sectAlign : config->sectionAlignments)
     if (sectAlign.segName == name && sectAlign.sectName == osec->name)
       osec->align = sectAlign.align;
 }
 

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;
+  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/PointerUnion.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:
   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?
 
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;
 };
 
-static_assert((CodeSignatureSection::blobHeadersSize % 8) == 0, "");
-static_assert((CodeSignatureSection::fixedHeadersSize % 8) == 0, "");
+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

 //===- 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"

 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 StringTableSection::writeTo(uint8_t *buf) const {
   uint32_t off = 0;
   for (StringRef str : strings) {
     memcpy(buf + off, str.data(), str.size());
     off += str.size() + 1; // account for null terminator
   }
 }
 
+static_assert((CodeSignatureSection::blobHeadersSize % 8) == 0, "");
+static_assert((CodeSignatureSection::fixedHeadersSize % 8) == 0, "");
+
 CodeSignatureSection::CodeSignatureSection()
     : LinkEditSection(segment_names::linkEdit, section_names::codeSignature) {
   align = 16; // required by libstuff
   fileName = config->outputFile;
   size_t slashIndex = fileName.rfind("/");
   if (slashIndex != std::string::npos)
     fileName = fileName.drop_front(slashIndex + 1);
   allHeadersSize = alignTo<16>(fixedHeadersSize + fileName.size() + 1);
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) {
+  flags = S_CSTRING_LITERALS; // FIXME merge flags properly
+}
+
+void CStringSection::addInput(CStringInputSection *isec) {
+  align = std::max(align, isec->align);
+  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.finalize();
+
+  // 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.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();
 void prepareCompactUnwind(InputSection *isec);
 
 } // 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) {
+  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

 //===- 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"
 
return StringSwitch<int>(seg->name)
       .Case(segment_names::pageZero, -4)
       .Case(segment_names::text, -3)
       .Case(segment_names::dataConst, -2)
       .Case(segment_names::data, -1)
       .Case(segment_names::llvm, std::numeric_limits<int>::max() - 1)
       // Make sure __LINKEDIT is the last segment (i.e. all its hidden
       // sections must be ordered after other sections).
       .Case(segment_names::linkEdit, std::numeric_limits<int>::max())
-      .Default(0);
+      .Default(seg->inputOrder);
 }
 
 static int sectionOrder(OutputSection *osec) {
   StringRef segname = osec->parent->name;
   // Sections are uniquely identified by their segment + section name.
   if (segname == segment_names::text) {
     return StringSwitch<int>(osec->name)
         .Case(section_names::header, -4)
         .Case(section_names::text, -3)
         .Case(section_names::stubs, -2)
         .Case(section_names::stubHelper, -1)
         .Case(section_names::unwindInfo, std::numeric_limits<int>::max() - 1)
         .Case(section_names::ehFrame, std::numeric_limits<int>::max())
-        .Default(0);
+        .Default(osec->inputOrder);
   } else if (segname == segment_names::data ||
              segname == segment_names::dataConst) {
     // For each thread spawned, dyld will initialize its TLVs by copying the
     // address range from the start of the first thread-local data section to
     // the end of the last one. We therefore arrange these sections contiguously
     // to minimize the amount of memory used. Additionally, since zerofill
     // sections must be at the end of their segments, and since TLV data
     // sections can be zerofills, we end up putting all TLV data sections at the
     // end of the segment.
     switch (sectionType(osec->flags)) {
     case S_THREAD_LOCAL_REGULAR:
       return std::numeric_limits<int>::max() - 2;
     case S_THREAD_LOCAL_ZEROFILL:
       return std::numeric_limits<int>::max() - 1;
     case S_ZEROFILL:
       return std::numeric_limits<int>::max();
     default:
       return StringSwitch<int>(osec->name)
+          .Case(section_names::got, -3)
           .Case(section_names::lazySymbolPtr, -2)
-          .Case(section_names::data, -1)
-          .Default(0);
+          .Case(section_names::const_, -1)
+          .Default(osec->inputOrder);
     }
   } else if (segname == segment_names::linkEdit) {
     return StringSwitch<int>(osec->name)
         .Case(section_names::rebase, -9)
         .Case(section_names::binding, -8)
         .Case(section_names::weakBinding, -7)
         .Case(section_names::lazyBinding, -6)
         .Case(section_names::export_, -5)
         .Case(section_names::functionStarts, -4)
         .Case(section_names::symbolTable, -3)
         .Case(section_names::indirectSymbolTable, -2)
         .Case(section_names::stringTable, -1)
         .Case(section_names::codeSignature, std::numeric_limits<int>::max())
-        .Default(0);
+        .Default(osec->inputOrder);
   }
   // ZeroFill sections must always be the at the end of their segments,
   // otherwise subsequent sections may get overwritten with zeroes at runtime.
   if (sectionType(osec->flags) == S_ZEROFILL)
     return std::numeric_limits<int>::max();
-  return 0;
+  return osec->inputOrder;
 }
 
 template <typename T, typename F>
 static std::function<bool(T, T)> compareByOrder(F ord) {
   return [=](T a, T b) { return ord(a) < ord(b); };
 }
 
 // Sorting only can happen once all outputs have been collected. Here we sort
 // segments, output sections within each segment, and input sections within each
 // output segment.
 static void sortSegmentsAndSections() {
   TimeTraceScope timeScope("Sort segments and sections");
 
-  llvm::stable_sort(outputSegments,
-                    compareByOrder<OutputSegment *>(segmentOrder));
+  llvm::sort(outputSegments, compareByOrder<OutputSegment *>(segmentOrder));
 
   DenseMap<const InputSection *, size_t> isecPriorities =
       buildInputSectionPriorities();
 
   uint32_t sectionIndex = 0;
   for (OutputSegment *seg : outputSegments) {
     seg->sortOutputSections(compareByOrder<OutputSection *>(sectionOrder));
     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;
-  for (InputSection *isec : inputSections) {
+  // Then add input sections to output sections.
+  DenseMap<NamePair, ConcatOutputSection *> mergedOutputSections;
+  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});
-    MergedOutputSection *&osec = mergedOutputSections[names];
-    if (osec == nullptr)
-      osec = make<MergedOutputSection>(names.second);
-    osec->mergeInput(isec);
+      ConcatOutputSection *&osec = mergedOutputSections[names];
+      if (osec == nullptr) {
+        osec = make<ConcatOutputSection>(names.second);
+        osec->inputOrder = p.index();
+      }
+      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 : mergedOutputSections) {
     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 (ssec->isNeeded()) {
       if (it == mergedOutputSections.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" --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.
+# CHECK:      Contents of (__TEXT,__cstring) section
+# CHECK-NEXT: bar
+# CHECK-NEXT: foo
+
+## Make sure both symbol and section relocations point to the right thing.
+# CHECK-NEXT: 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
+# CHECK-NEXT: __TEXT:__cstring:bar
+# CHECK-NEXT: __TEXT:__cstring:ar
+# CHECK-NEXT: __TEXT:__cstring:r
+
+## 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
+# CHECK-DAG: [[#BAR+1]]      l     O __TEXT,__cstring _ar
+# CHECK-DAG: [[#BAR+2]]      l     O __TEXT,__cstring _r
+
+## 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"
+_ar:
+  .asciz "ar"
+_r:
+  .asciz "r"
+
+.text
+movq _r@GOTPCREL(%rip), %rax
+
+.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
+.quad _ar
+.quad _r
+
+#--- 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 a cstring_literals section, so LLD cannot do string 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/load-command-sequence.s

 # COMMON: cmd LC_SEGMENT_64
 # COMMON: segname __TEXT
 # COMMON: sectname __text
 # COMMON: segname __TEXT
 # COMMON: sectname __cstring
 # COMMON: segname __TEXT
 # COMMON: cmd LC_SEGMENT_64
 # COMMON: segname __DATA_CONST
-# COMMON: sectname __const
-# COMMON: segname __DATA_CONST
 # COMMON: sectname __got
 # COMMON: segname __DATA_CONST
+# COMMON: sectname __const
+# COMMON: segname __DATA_CONST
 # COMMON: cmd LC_SEGMENT_64
 # COMMON: segname __DATA
 # COMMON: sectname __data
 # COMMON: segname __DATA
 # COMMON: cmd LC_SEGMENT_64
 # COMMON: segname __LINKEDIT
 # COMMON: cmd LC_DYLD_INFO_ONLY
 # COMMON: cmd LC_SYMTAB

lld/test/MachO/section-order.s

+# REQUIRES: x86
+## Check that section ordering follows from input file ordering.
+# RUN: rm -rf %t; split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/1.s -o %t/1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/2.s -o %t/2.o
+# RUN: %lld -dylib %t/1.o %t/2.o -o %t/12
+# RUN: %lld -dylib %t/2.o %t/1.o -o %t/21
+# RUN: llvm-objdump --macho --section-headers %t/12 | FileCheck %s --check-prefix=CHECK-12
+# RUN: llvm-objdump --macho --section-headers %t/21 | FileCheck %s --check-prefix=CHECK-21
+
+# CHECK-12:      __text
+# CHECK-12-NEXT: foo
+# CHECK-12-NEXT: bar
+# CHECK-12-NEXT: __cstring
+
+# CHECK-21:      __text
+# CHECK-21-NEXT: __cstring
+# CHECK-21-NEXT: bar
+# CHECK-21-NEXT: foo
+
+#--- 1.s
+.section __TEXT,foo
+  .space 1
+.section __TEXT,bar
+  .space 1
+.cstring
+  .asciz ""
+
+#--- 2.s
+.cstring
+  .asciz ""
+.section __TEXT,bar
+  .space 1
+.section __TEXT,foo
+  .space 1

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/weak-binding.s

 # CHECK-LABEL: Rebase table:
 # CHECK:       __DATA        __la_symbol_ptr 0x[[#%x,WEAK_EXT_FN:]]  pointer
 
 # CHECK-LABEL: Bind table:
 # CHECK-DAG:   __DATA_CONST  __got           0x[[#WEAK_DY_GOT_ADDR]] pointer 0 libfoo    _weak_dysym_for_gotpcrel
 # CHECK-DAG:   __DATA        __la_symbol_ptr 0x[[#%x,WEAK_DY_FN:]]   pointer 0 libfoo    _weak_dysym_fn
 # CHECK-DAG:   __DATA        __data          0x[[#%x,WEAK_DY:]]      pointer 0 libfoo    _weak_dysym
 # CHECK-DAG:   __DATA        __thread_vars   0x{{[0-9a-f]*}}         pointer 0 libSystem __tlv_bootstrap
+# CHECK-DAG:   __DATA        __thread_vars   0x{{[0-9a-f]*}}         pointer 0 libSystem __tlv_bootstrap
 # CHECK-DAG:   __DATA        __thread_ptrs   0x[[#WEAK_DY_TLV_ADDR]] pointer 0 libfoo    _weak_dysym_tlv
-## Check that we don't have any other bindings
+## FIXME: This was supposed to check that we don't have any other bindings in
+## the bind table, but in practice it just checks that we don't have a binding
+## immediately after the last -DAG match...
 # CHECK-NOT:   pointer
 
 # CHECK-LABEL: Lazy bind table:
 ## Verify that we have no lazy bindings
 # CHECK-NOT:   pointer
 
 # CHECK-LABEL: Weak bind table:
 # CHECK-DAG:   __DATA_CONST __got           0x[[#WEAK_DY_GOT_ADDR]]   pointer 0 _weak_dysym_for_gotpcrel

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