--- a/lld/MachO/Writer.cpp	Mon May 25 11:55:54 2020 +0900
+++ b/lld/MachO/Writer.cpp	Tue Jun 08 06:07:14 2021 +0900
@@ -7,68 +7,86 @@
 //===----------------------------------------------------------------------===//
 
 #include "Writer.h"
+#include "ConcatOutputSection.h"
 #include "Config.h"
 #include "InputFiles.h"
 #include "InputSection.h"
-#include "MergedOutputSection.h"
+#include "MapFile.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
+#include "UnwindInfoSection.h"
 
+#include "lld/Common/Arrays.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/MachO.h"
+#include "llvm/Config/llvm-config.h"
 #include "llvm/Support/LEB128.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/Parallel.h"
 #include "llvm/Support/Path.h"
+#include "llvm/Support/TimeProfiler.h"
+#include "llvm/Support/xxhash.h"
+
+#include <algorithm>
 
 using namespace llvm;
 using namespace llvm::MachO;
+using namespace llvm::sys;
 using namespace lld;
 using namespace lld::macho;
 
 namespace {
-class LCLinkEdit;
-class LCDyldInfo;
-class LCSymtab;
+class LCUuid;
 
 class Writer {
 public:
   Writer() : buffer(errorHandler().outputBuffer) {}
 
   void scanRelocations();
-  void createOutputSections();
-  void createLoadCommands();
+  void scanSymbols();
+  template <class LP> void createOutputSections();
+  template <class LP> void createLoadCommands();
+  void finalizeAddresses();
+  void finalizeLinkEditSegment();
   void assignAddresses(OutputSegment *);
-  void createSymtabContents();
 
   void openFile();
   void writeSections();
+  void writeUuid();
+  void writeCodeSignature();
+  void writeOutputFile();
 
-  void run();
+  template <class LP> void run();
 
   std::unique_ptr<FileOutputBuffer> &buffer;
   uint64_t addr = 0;
   uint64_t fileOff = 0;
-  MachHeaderSection *headerSection = nullptr;
-  BindingSection *bindingSection = nullptr;
-  LazyBindingSection *lazyBindingSection = nullptr;
-  ExportSection *exportSection = nullptr;
+  MachHeaderSection *header = nullptr;
   StringTableSection *stringTableSection = nullptr;
   SymtabSection *symtabSection = nullptr;
+  IndirectSymtabSection *indirectSymtabSection = nullptr;
+  CodeSignatureSection *codeSignatureSection = nullptr;
+  FunctionStartsSection *functionStartsSection = nullptr;
+
+  LCUuid *uuidCommand = nullptr;
+  OutputSegment *linkEditSegment = nullptr;
 };
 
 // LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 class LCDyldInfo : public LoadCommand {
 public:
-  LCDyldInfo(BindingSection *bindingSection,
+  LCDyldInfo(RebaseSection *rebaseSection, BindingSection *bindingSection,
+             WeakBindingSection *weakBindingSection,
              LazyBindingSection *lazyBindingSection,
              ExportSection *exportSection)
-      : bindingSection(bindingSection), lazyBindingSection(lazyBindingSection),
-        exportSection(exportSection) {}
+      : rebaseSection(rebaseSection), bindingSection(bindingSection),
+        weakBindingSection(weakBindingSection),
+        lazyBindingSection(lazyBindingSection), exportSection(exportSection) {}
 
   uint32_t getSize() const override { return sizeof(dyld_info_command); }
 
@@ -76,10 +94,18 @@
     auto *c = reinterpret_cast<dyld_info_command *>(buf);
     c->cmd = LC_DYLD_INFO_ONLY;
     c->cmdsize = getSize();
+    if (rebaseSection->isNeeded()) {
+      c->rebase_off = rebaseSection->fileOff;
+      c->rebase_size = rebaseSection->getFileSize();
+    }
     if (bindingSection->isNeeded()) {
       c->bind_off = bindingSection->fileOff;
       c->bind_size = bindingSection->getFileSize();
     }
+    if (weakBindingSection->isNeeded()) {
+      c->weak_bind_off = weakBindingSection->fileOff;
+      c->weak_bind_size = weakBindingSection->getFileSize();
+    }
     if (lazyBindingSection->isNeeded()) {
       c->lazy_bind_off = lazyBindingSection->fileOff;
       c->lazy_bind_size = lazyBindingSection->getFileSize();
@@ -90,36 +116,77 @@
     }
   }
 
+  RebaseSection *rebaseSection;
   BindingSection *bindingSection;
+  WeakBindingSection *weakBindingSection;
   LazyBindingSection *lazyBindingSection;
   ExportSection *exportSection;
 };
 
+class LCFunctionStarts : public LoadCommand {
+public:
+  explicit LCFunctionStarts(FunctionStartsSection *functionStartsSection)
+      : functionStartsSection(functionStartsSection) {}
+
+  uint32_t getSize() const override { return sizeof(linkedit_data_command); }
+
+  void writeTo(uint8_t *buf) const override {
+    auto *c = reinterpret_cast<linkedit_data_command *>(buf);
+    c->cmd = LC_FUNCTION_STARTS;
+    c->cmdsize = getSize();
+    c->dataoff = functionStartsSection->fileOff;
+    c->datasize = functionStartsSection->getFileSize();
+  }
+
+private:
+  FunctionStartsSection *functionStartsSection;
+};
+
 class LCDysymtab : public LoadCommand {
 public:
+  LCDysymtab(SymtabSection *symtabSection,
+             IndirectSymtabSection *indirectSymtabSection)
+      : symtabSection(symtabSection),
+        indirectSymtabSection(indirectSymtabSection) {}
+
   uint32_t getSize() const override { return sizeof(dysymtab_command); }
 
   void writeTo(uint8_t *buf) const override {
     auto *c = reinterpret_cast<dysymtab_command *>(buf);
     c->cmd = LC_DYSYMTAB;
     c->cmdsize = getSize();
+
+    c->ilocalsym = 0;
+    c->iextdefsym = c->nlocalsym = symtabSection->getNumLocalSymbols();
+    c->nextdefsym = symtabSection->getNumExternalSymbols();
+    c->iundefsym = c->iextdefsym + c->nextdefsym;
+    c->nundefsym = symtabSection->getNumUndefinedSymbols();
+
+    c->indirectsymoff = indirectSymtabSection->fileOff;
+    c->nindirectsyms = indirectSymtabSection->getNumSymbols();
   }
+
+  SymtabSection *symtabSection;
+  IndirectSymtabSection *indirectSymtabSection;
 };
 
-class LCSegment : public LoadCommand {
+template <class LP> class LCSegment : public LoadCommand {
 public:
   LCSegment(StringRef name, OutputSegment *seg) : name(name), seg(seg) {}
 
   uint32_t getSize() const override {
-    return sizeof(segment_command_64) +
-           seg->numNonHiddenSections() * sizeof(section_64);
+    return sizeof(typename LP::segment_command) +
+           seg->numNonHiddenSections() * sizeof(typename LP::section);
   }
 
   void writeTo(uint8_t *buf) const override {
-    auto *c = reinterpret_cast<segment_command_64 *>(buf);
-    buf += sizeof(segment_command_64);
+    using SegmentCommand = typename LP::segment_command;
+    using Section = typename LP::section;
 
-    c->cmd = LC_SEGMENT_64;
+    auto *c = reinterpret_cast<SegmentCommand *>(buf);
+    buf += sizeof(SegmentCommand);
+
+    c->cmd = LP::segmentLCType;
     c->cmdsize = getSize();
     memcpy(c->segname, name.data(), name.size());
     c->fileoff = seg->fileOff;
@@ -130,29 +197,27 @@
       return;
 
     c->vmaddr = seg->firstSection()->addr;
-    c->vmsize =
-        seg->lastSection()->addr + seg->lastSection()->getSize() - c->vmaddr;
+    c->vmsize = seg->vmSize;
+    c->filesize = seg->fileSize;
     c->nsects = seg->numNonHiddenSections();
 
-    for (auto &p : seg->getSections()) {
-      StringRef s = p.first;
-      OutputSection *section = p.second;
-      c->filesize += section->getFileSize();
-
-      if (section->isHidden())
+    for (const OutputSection *osec : seg->getSections()) {
+      if (osec->isHidden())
         continue;
 
-      auto *sectHdr = reinterpret_cast<section_64 *>(buf);
-      buf += sizeof(section_64);
+      auto *sectHdr = reinterpret_cast<Section *>(buf);
+      buf += sizeof(Section);
 
-      memcpy(sectHdr->sectname, s.data(), s.size());
+      memcpy(sectHdr->sectname, osec->name.data(), osec->name.size());
       memcpy(sectHdr->segname, name.data(), name.size());
 
-      sectHdr->addr = section->addr;
-      sectHdr->offset = section->fileOff;
-      sectHdr->align = Log2_32(section->align);
-      sectHdr->flags = section->flags;
-      sectHdr->size = section->getSize();
+      sectHdr->addr = osec->addr;
+      sectHdr->offset = osec->fileOff;
+      sectHdr->align = Log2_32(osec->align);
+      sectHdr->flags = osec->flags;
+      sectHdr->size = osec->getSize();
+      sectHdr->reserved1 = osec->reserved1;
+      sectHdr->reserved2 = osec->reserved2;
     }
   }
 
@@ -162,13 +227,21 @@
 };
 
 class LCMain : public LoadCommand {
-  uint32_t getSize() const override { return sizeof(entry_point_command); }
+  uint32_t getSize() const override {
+    return sizeof(structs::entry_point_command);
+  }
 
   void writeTo(uint8_t *buf) const override {
-    auto *c = reinterpret_cast<entry_point_command *>(buf);
+    auto *c = reinterpret_cast<structs::entry_point_command *>(buf);
     c->cmd = LC_MAIN;
     c->cmdsize = getSize();
-    c->entryoff = config->entry->getVA() - ImageBase;
+
+    if (config->entry->isInStubs())
+      c->entryoff =
+          in.stubs->fileOff + config->entry->stubsIndex * target->stubSize;
+    else
+      c->entryoff = config->entry->getFileOffset();
+
     c->stacksize = 0;
   }
 };
@@ -200,7 +273,12 @@
 //   * LC_REEXPORT_DYLIB
 class LCDylib : public LoadCommand {
 public:
-  LCDylib(LoadCommandType type, StringRef path) : type(type), path(path) {}
+  LCDylib(LoadCommandType type, StringRef path,
+          uint32_t compatibilityVersion = 0, uint32_t currentVersion = 0)
+      : type(type), path(path), compatibilityVersion(compatibilityVersion),
+        currentVersion(currentVersion) {
+    instanceCount++;
+  }
 
   uint32_t getSize() const override {
     return alignTo(sizeof(dylib_command) + path.size() + 1, 8);
@@ -213,16 +291,26 @@
     c->cmd = type;
     c->cmdsize = getSize();
     c->dylib.name = sizeof(dylib_command);
+    c->dylib.timestamp = 0;
+    c->dylib.compatibility_version = compatibilityVersion;
+    c->dylib.current_version = currentVersion;
 
     memcpy(buf, path.data(), path.size());
     buf[path.size()] = '\0';
   }
 
+  static uint32_t getInstanceCount() { return instanceCount; }
+
 private:
   LoadCommandType type;
   StringRef path;
+  uint32_t compatibilityVersion;
+  uint32_t currentVersion;
+  static uint32_t instanceCount;
 };
 
+uint32_t LCDylib::instanceCount = 0;
+
 class LCLoadDylinker : public LoadCommand {
 public:
   uint32_t getSize() const override {
@@ -246,60 +334,431 @@
   // different location.
   const StringRef path = "/usr/lib/dyld";
 };
+
+class LCRPath : public LoadCommand {
+public:
+  explicit LCRPath(StringRef path) : path(path) {}
+
+  uint32_t getSize() const override {
+    return alignTo(sizeof(rpath_command) + path.size() + 1, target->wordSize);
+  }
+
+  void writeTo(uint8_t *buf) const override {
+    auto *c = reinterpret_cast<rpath_command *>(buf);
+    buf += sizeof(rpath_command);
+
+    c->cmd = LC_RPATH;
+    c->cmdsize = getSize();
+    c->path = sizeof(rpath_command);
+
+    memcpy(buf, path.data(), path.size());
+    buf[path.size()] = '\0';
+  }
+
+private:
+  StringRef path;
+};
+
+class LCMinVersion : public LoadCommand {
+public:
+  explicit LCMinVersion(const PlatformInfo &platformInfo)
+      : platformInfo(platformInfo) {}
+
+  uint32_t getSize() const override { return sizeof(version_min_command); }
+
+  void writeTo(uint8_t *buf) const override {
+    auto *c = reinterpret_cast<version_min_command *>(buf);
+    switch (platformInfo.target.Platform) {
+    case PlatformKind::macOS:
+      c->cmd = LC_VERSION_MIN_MACOSX;
+      break;
+    case PlatformKind::iOS:
+    case PlatformKind::iOSSimulator:
+      c->cmd = LC_VERSION_MIN_IPHONEOS;
+      break;
+    case PlatformKind::tvOS:
+    case PlatformKind::tvOSSimulator:
+      c->cmd = LC_VERSION_MIN_TVOS;
+      break;
+    case PlatformKind::watchOS:
+    case PlatformKind::watchOSSimulator:
+      c->cmd = LC_VERSION_MIN_WATCHOS;
+      break;
+    default:
+      llvm_unreachable("invalid platform");
+      break;
+    }
+    c->cmdsize = getSize();
+    c->version = encodeVersion(platformInfo.minimum);
+    c->sdk = encodeVersion(platformInfo.sdk);
+  }
+
+private:
+  const PlatformInfo &platformInfo;
+};
+
+class LCBuildVersion : public LoadCommand {
+public:
+  explicit LCBuildVersion(const PlatformInfo &platformInfo)
+      : platformInfo(platformInfo) {}
+
+  const int ntools = 1;
+
+  uint32_t getSize() const override {
+    return sizeof(build_version_command) + ntools * sizeof(build_tool_version);
+  }
+
+  void writeTo(uint8_t *buf) const override {
+    auto *c = reinterpret_cast<build_version_command *>(buf);
+    c->cmd = LC_BUILD_VERSION;
+    c->cmdsize = getSize();
+    c->platform = static_cast<uint32_t>(platformInfo.target.Platform);
+    c->minos = encodeVersion(platformInfo.minimum);
+    c->sdk = encodeVersion(platformInfo.sdk);
+    c->ntools = ntools;
+    auto *t = reinterpret_cast<build_tool_version *>(&c[1]);
+    t->tool = TOOL_LD;
+    t->version = encodeVersion(llvm::VersionTuple(
+        LLVM_VERSION_MAJOR, LLVM_VERSION_MINOR, LLVM_VERSION_PATCH));
+  }
+
+private:
+  const PlatformInfo &platformInfo;
+};
+
+// Stores a unique identifier for the output file based on an MD5 hash of its
+// contents. In order to hash the contents, we must first write them, but
+// LC_UUID itself must be part of the written contents in order for all the
+// offsets to be calculated correctly. We resolve this circular paradox by
+// first writing an LC_UUID with an all-zero UUID, then updating the UUID with
+// its real value later.
+class LCUuid : public LoadCommand {
+public:
+  uint32_t getSize() const override { return sizeof(uuid_command); }
+
+  void writeTo(uint8_t *buf) const override {
+    auto *c = reinterpret_cast<uuid_command *>(buf);
+    c->cmd = LC_UUID;
+    c->cmdsize = getSize();
+    uuidBuf = c->uuid;
+  }
+
+  void writeUuid(uint64_t digest) const {
+    // xxhash only gives us 8 bytes, so put some fixed data in the other half.
+    static_assert(sizeof(uuid_command::uuid) == 16, "unexpected uuid size");
+    memcpy(uuidBuf, "LLD\xa1UU1D", 8);
+    memcpy(uuidBuf + 8, &digest, 8);
+
+    // RFC 4122 conformance. We need to fix 4 bits in byte 6 and 2 bits in
+    // byte 8. Byte 6 is already fine due to the fixed data we put in. We don't
+    // want to lose bits of the digest in byte 8, so swap that with a byte of
+    // fixed data that happens to have the right bits set.
+    std::swap(uuidBuf[3], uuidBuf[8]);
+
+    // Claim that this is an MD5-based hash. It isn't, but this signals that
+    // this is not a time-based and not a random hash. MD5 seems like the least
+    // bad lie we can put here.
+    assert((uuidBuf[6] & 0xf0) == 0x30 && "See RFC 4122 Sections 4.2.2, 4.1.3");
+    assert((uuidBuf[8] & 0xc0) == 0x80 && "See RFC 4122 Section 4.2.2");
+  }
+
+  mutable uint8_t *uuidBuf;
+};
+
+template <class LP> class LCEncryptionInfo : public LoadCommand {
+public:
+  uint32_t getSize() const override {
+    return sizeof(typename LP::encryption_info_command);
+  }
+
+  void writeTo(uint8_t *buf) const override {
+    using EncryptionInfo = typename LP::encryption_info_command;
+    auto *c = reinterpret_cast<EncryptionInfo *>(buf);
+    buf += sizeof(EncryptionInfo);
+    c->cmd = LP::encryptionInfoLCType;
+    c->cmdsize = getSize();
+    c->cryptoff = in.header->getSize();
+    auto it = find_if(outputSegments, [](const OutputSegment *seg) {
+      return seg->name == segment_names::text;
+    });
+    assert(it != outputSegments.end());
+    c->cryptsize = (*it)->fileSize - c->cryptoff;
+  }
+};
+
+class LCCodeSignature : public LoadCommand {
+public:
+  LCCodeSignature(CodeSignatureSection *section) : section(section) {}
+
+  uint32_t getSize() const override { return sizeof(linkedit_data_command); }
+
+  void writeTo(uint8_t *buf) const override {
+    auto *c = reinterpret_cast<linkedit_data_command *>(buf);
+    c->cmd = LC_CODE_SIGNATURE;
+    c->cmdsize = getSize();
+    c->dataoff = static_cast<uint32_t>(section->fileOff);
+    c->datasize = section->getSize();
+  }
+
+  CodeSignatureSection *section;
+};
+
 } // namespace
 
+// Add stubs and bindings where necessary (e.g. if the symbol is a
+// DylibSymbol.)
+static void prepareBranchTarget(Symbol *sym) {
+  if (auto *dysym = dyn_cast<DylibSymbol>(sym)) {
+    if (in.stubs->addEntry(dysym)) {
+      if (sym->isWeakDef()) {
+        in.binding->addEntry(dysym, in.lazyPointers->isec,
+                             sym->stubsIndex * target->wordSize);
+        in.weakBinding->addEntry(sym, in.lazyPointers->isec,
+                                 sym->stubsIndex * target->wordSize);
+      } else {
+        in.lazyBinding->addEntry(dysym);
+      }
+    }
+  } else if (auto *defined = dyn_cast<Defined>(sym)) {
+    if (defined->isExternalWeakDef()) {
+      if (in.stubs->addEntry(sym)) {
+        in.rebase->addEntry(in.lazyPointers->isec,
+                            sym->stubsIndex * target->wordSize);
+        in.weakBinding->addEntry(sym, in.lazyPointers->isec,
+                                 sym->stubsIndex * target->wordSize);
+      }
+    }
+  } else {
+    llvm_unreachable("invalid branch target symbol type");
+  }
+}
+
+// Can a symbol's address can only be resolved at runtime?
+static bool needsBinding(const Symbol *sym) {
+  if (isa<DylibSymbol>(sym))
+    return true;
+  if (const auto *defined = dyn_cast<Defined>(sym))
+    return defined->isExternalWeakDef();
+  return false;
+}
+
+static void prepareSymbolRelocation(Symbol *sym, const InputSection *isec,
+                                    const Reloc &r) {
+  const RelocAttrs &relocAttrs = target->getRelocAttrs(r.type);
+
+  if (relocAttrs.hasAttr(RelocAttrBits::BRANCH)) {
+    prepareBranchTarget(sym);
+  } else if (relocAttrs.hasAttr(RelocAttrBits::GOT)) {
+    if (relocAttrs.hasAttr(RelocAttrBits::POINTER) || needsBinding(sym))
+      in.got->addEntry(sym);
+  } else if (relocAttrs.hasAttr(RelocAttrBits::TLV)) {
+    if (needsBinding(sym))
+      in.tlvPointers->addEntry(sym);
+  } else if (relocAttrs.hasAttr(RelocAttrBits::UNSIGNED)) {
+    // References from thread-local variable sections are treated as offsets
+    // relative to the start of the referent section, and therefore have no
+    // need of rebase opcodes.
+    if (!(isThreadLocalVariables(isec->flags) && isa<Defined>(sym)))
+      addNonLazyBindingEntries(sym, isec, r.offset, r.addend);
+  }
+}
+
 void Writer::scanRelocations() {
-  for (InputSection *sect : inputSections)
-    for (Reloc &r : sect->relocs)
-      if (auto *s = r.target.dyn_cast<Symbol *>())
-        if (auto *dylibSymbol = dyn_cast<DylibSymbol>(s))
-          target->prepareDylibSymbolRelocation(*dylibSymbol, r.type);
+  TimeTraceScope timeScope("Scan relocations");
+  for (InputSection *isec : inputSections) {
+    if (isec->shouldOmitFromOutput())
+      continue;
+
+    if (isec->segname == segment_names::ld) {
+      in.unwindInfo->prepareRelocations(isec);
+      continue;
+    }
+
+    for (auto it = isec->relocs.begin(); it != isec->relocs.end(); ++it) {
+      Reloc &r = *it;
+      if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
+        // Skip over the following UNSIGNED relocation -- it's just there as the
+        // minuend, and doesn't have the usual UNSIGNED semantics. We don't want
+        // to emit rebase opcodes for it.
+        it++;
+        continue;
+      }
+      if (auto *sym = r.referent.dyn_cast<Symbol *>()) {
+        if (auto *undefined = dyn_cast<Undefined>(sym))
+          treatUndefinedSymbol(*undefined);
+        // treatUndefinedSymbol() can replace sym with a DylibSymbol; re-check.
+        if (!isa<Undefined>(sym) && validateSymbolRelocation(sym, isec, r))
+          prepareSymbolRelocation(sym, isec, r);
+      } else {
+        assert(r.referent.is<InputSection *>());
+        assert(!r.referent.get<InputSection *>()->shouldOmitFromOutput());
+        if (!r.pcrel)
+          in.rebase->addEntry(isec, r.offset);
+      }
+    }
+  }
 }
 
-void Writer::createLoadCommands() {
-  headerSection->addLoadCommand(
-      make<LCDyldInfo>(bindingSection, lazyBindingSection, exportSection));
-  headerSection->addLoadCommand(
-      make<LCSymtab>(symtabSection, stringTableSection));
-  headerSection->addLoadCommand(make<LCDysymtab>());
+void Writer::scanSymbols() {
+  TimeTraceScope timeScope("Scan symbols");
+  for (const Symbol *sym : symtab->getSymbols()) {
+    if (const auto *defined = dyn_cast<Defined>(sym)) {
+      if (defined->overridesWeakDef && defined->isLive())
+        in.weakBinding->addNonWeakDefinition(defined);
+    } else if (const auto *dysym = dyn_cast<DylibSymbol>(sym)) {
+      // This branch intentionally doesn't check isLive().
+      if (dysym->isDynamicLookup())
+        continue;
+      dysym->getFile()->refState =
+          std::max(dysym->getFile()->refState, dysym->getRefState());
+    }
+  }
+}
+
+// TODO: ld64 enforces the old load commands in a few other cases.
+static bool useLCBuildVersion(const PlatformInfo &platformInfo) {
+  static const std::map<PlatformKind, llvm::VersionTuple> minVersion = {
+      {PlatformKind::macOS, llvm::VersionTuple(10, 14)},
+      {PlatformKind::iOS, llvm::VersionTuple(12, 0)},
+      {PlatformKind::iOSSimulator, llvm::VersionTuple(13, 0)},
+      {PlatformKind::tvOS, llvm::VersionTuple(12, 0)},
+      {PlatformKind::tvOSSimulator, llvm::VersionTuple(13, 0)},
+      {PlatformKind::watchOS, llvm::VersionTuple(5, 0)},
+      {PlatformKind::watchOSSimulator, llvm::VersionTuple(6, 0)}};
+  auto it = minVersion.find(platformInfo.target.Platform);
+  return it == minVersion.end() ? true : platformInfo.minimum >= it->second;
+}
+
+template <class LP> void Writer::createLoadCommands() {
+  uint8_t segIndex = 0;
+  for (OutputSegment *seg : outputSegments) {
+    in.header->addLoadCommand(make<LCSegment<LP>>(seg->name, seg));
+    seg->index = segIndex++;
+  }
+
+  in.header->addLoadCommand(make<LCDyldInfo>(
+      in.rebase, in.binding, in.weakBinding, in.lazyBinding, in.exports));
+  in.header->addLoadCommand(make<LCSymtab>(symtabSection, stringTableSection));
+  in.header->addLoadCommand(
+      make<LCDysymtab>(symtabSection, indirectSymtabSection));
+  if (functionStartsSection)
+    in.header->addLoadCommand(make<LCFunctionStarts>(functionStartsSection));
+  if (config->emitEncryptionInfo)
+    in.header->addLoadCommand(make<LCEncryptionInfo<LP>>());
+  for (StringRef path : config->runtimePaths)
+    in.header->addLoadCommand(make<LCRPath>(path));
 
   switch (config->outputType) {
   case MH_EXECUTE:
-    headerSection->addLoadCommand(make<LCMain>());
-    headerSection->addLoadCommand(make<LCLoadDylinker>());
+    in.header->addLoadCommand(make<LCLoadDylinker>());
+    in.header->addLoadCommand(make<LCMain>());
     break;
   case MH_DYLIB:
-    headerSection->addLoadCommand(
-        make<LCDylib>(LC_ID_DYLIB, config->installName));
+    in.header->addLoadCommand(make<LCDylib>(LC_ID_DYLIB, config->installName,
+                                            config->dylibCompatibilityVersion,
+                                            config->dylibCurrentVersion));
+    break;
+  case MH_BUNDLE:
     break;
   default:
     llvm_unreachable("unhandled output file type");
   }
 
-  uint8_t segIndex = 0;
-  for (OutputSegment *seg : outputSegments) {
-    headerSection->addLoadCommand(make<LCSegment>(seg->name, seg));
-    seg->index = segIndex++;
-  }
+  uuidCommand = make<LCUuid>();
+  in.header->addLoadCommand(uuidCommand);
 
-  uint64_t dylibOrdinal = 1;
+  if (useLCBuildVersion(config->platformInfo))
+    in.header->addLoadCommand(make<LCBuildVersion>(config->platformInfo));
+  else
+    in.header->addLoadCommand(make<LCMinVersion>(config->platformInfo));
+
+  int64_t dylibOrdinal = 1;
+  DenseMap<StringRef, int64_t> ordinalForInstallName;
   for (InputFile *file : inputFiles) {
     if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
-      headerSection->addLoadCommand(
-          make<LCDylib>(LC_LOAD_DYLIB, dylibFile->dylibName));
-      dylibFile->ordinal = dylibOrdinal++;
+      if (dylibFile->isBundleLoader) {
+        dylibFile->ordinal = BIND_SPECIAL_DYLIB_MAIN_EXECUTABLE;
+        // Shortcut since bundle-loader does not re-export the symbols.
+
+        dylibFile->reexport = false;
+        continue;
+      }
+
+      // Don't emit load commands for a dylib that is not referenced if:
+      // - it was added implicitly (via a reexport, an LC_LOAD_DYLINKER --
+      //   if it's on the linker command line, it's explicit)
+      // - or it's marked MH_DEAD_STRIPPABLE_DYLIB
+      // - or the flag -dead_strip_dylibs is used
+      // FIXME: `isReferenced()` is currently computed before dead code
+      // stripping, so references from dead code keep a dylib alive. This
+      // matches ld64, but it's something we should do better.
+      if (!dylibFile->isReferenced() && !dylibFile->forceNeeded &&
+          (!dylibFile->explicitlyLinked || dylibFile->deadStrippable ||
+           config->deadStripDylibs))
+        continue;
+
+      // Several DylibFiles can have the same installName. Only emit a single
+      // load command for that installName and give all these DylibFiles the
+      // same ordinal.
+      // This can happen in several cases:
+      // - a new framework could change its installName to an older
+      //   framework name via an $ld$ symbol depending on platform_version
+      // - symlinks (for example, libpthread.tbd is a symlink to libSystem.tbd;
+      //   Foo.framework/Foo.tbd is usually a symlink to
+      //   Foo.framework/Versions/Current/Foo.tbd, where
+      //   Foo.framework/Versions/Current is usually a symlink to
+      //   Foo.framework/Versions/A)
+      // - a framework can be linked both explicitly on the linker
+      //   command line and implicitly as a reexport from a different
+      //   framework. The re-export will usually point to the tbd file
+      //   in Foo.framework/Versions/A/Foo.tbd, while the explicit link will
+      //   usually find Foo.framwork/Foo.tbd. These are usually symlinks,
+      //   but in a --reproduce archive they will be identical but distinct
+      //   files.
+      // In the first case, *semantically distinct* DylibFiles will have the
+      // same installName.
+      int64_t &ordinal = ordinalForInstallName[dylibFile->installName];
+      if (ordinal) {
+        dylibFile->ordinal = ordinal;
+        continue;
+      }
+
+      ordinal = dylibFile->ordinal = dylibOrdinal++;
+      LoadCommandType lcType =
+          dylibFile->forceWeakImport || dylibFile->refState == RefState::Weak
+              ? LC_LOAD_WEAK_DYLIB
+              : LC_LOAD_DYLIB;
+      in.header->addLoadCommand(make<LCDylib>(lcType, dylibFile->installName,
+                                              dylibFile->compatibilityVersion,
+                                              dylibFile->currentVersion));
 
       if (dylibFile->reexport)
-        headerSection->addLoadCommand(
-            make<LCDylib>(LC_REEXPORT_DYLIB, dylibFile->dylibName));
+        in.header->addLoadCommand(
+            make<LCDylib>(LC_REEXPORT_DYLIB, dylibFile->installName));
     }
   }
+
+  if (codeSignatureSection)
+    in.header->addLoadCommand(make<LCCodeSignature>(codeSignatureSection));
+
+  const uint32_t MACOS_MAXPATHLEN = 1024;
+  config->headerPad = std::max(
+      config->headerPad, (config->headerPadMaxInstallNames
+                              ? LCDylib::getInstanceCount() * MACOS_MAXPATHLEN
+                              : 0));
 }
 
 static size_t getSymbolPriority(const SymbolPriorityEntry &entry,
-                                const InputFile &file) {
-  return std::max(entry.objectFiles.lookup(sys::path::filename(file.getName())),
-                  entry.anyObjectFile);
+                                const InputFile *f) {
+  // We don't use toString(InputFile *) here because it returns the full path
+  // for object files, and we only want the basename.
+  StringRef filename;
+  if (f->archiveName.empty())
+    filename = path::filename(f->getName());
+  else
+    filename = saver.save(path::filename(f->archiveName) + "(" +
+                          path::filename(f->getName()) + ")");
+  return std::max(entry.objectFiles.lookup(filename), entry.anyObjectFile);
 }
 
 // Each section gets assigned the priority of the highest-priority symbol it
@@ -317,15 +776,16 @@
 
     SymbolPriorityEntry &entry = it->second;
     size_t &priority = sectionPriorities[sym.isec];
-    priority = std::max(priority, getSymbolPriority(entry, *sym.isec->file));
+    priority = std::max(priority, getSymbolPriority(entry, sym.isec->file));
   };
 
   // TODO: Make sure this handles weak symbols correctly.
-  for (InputFile *file : inputFiles)
-    if (isa<ObjFile>(file) || isa<ArchiveFile>(file))
+  for (const InputFile *file : inputFiles) {
+    if (isa<ObjFile>(file))
       for (Symbol *sym : file->symbols)
-        if (auto *d = dyn_cast<Defined>(sym))
+        if (auto *d = dyn_cast_or_null<Defined>(sym))
           addSym(*d);
+  }
 
   return sectionPriorities;
 }
@@ -334,24 +794,25 @@
 // segments, output sections within each segment, and input sections within each
 // output segment.
 static void sortSegmentsAndSections() {
-  auto comparator = OutputSegmentComparator();
-  llvm::stable_sort(outputSegments, comparator);
+  TimeTraceScope timeScope("Sort segments and sections");
+  sortOutputSegments();
 
   DenseMap<const InputSection *, size_t> isecPriorities =
       buildInputSectionPriorities();
 
   uint32_t sectionIndex = 0;
   for (OutputSegment *seg : outputSegments) {
-    seg->sortOutputSections(&comparator);
-    for (auto &p : seg->getSections()) {
-      OutputSection *section = p.second;
+    seg->sortOutputSections();
+    for (OutputSection *osec : seg->getSections()) {
       // Now that the output sections are sorted, assign the final
       // output section indices.
-      if (!section->isHidden())
-        section->index = ++sectionIndex;
+      if (!osec->isHidden())
+        osec->index = ++sectionIndex;
+      if (!firstTLVDataSection && isThreadLocalData(osec->flags))
+        firstTLVDataSection = osec;
 
       if (!isecPriorities.empty()) {
-        if (auto *merged = dyn_cast<MergedOutputSection>(section)) {
+        if (auto *merged = dyn_cast<ConcatOutputSection>(osec)) {
           llvm::stable_sort(merged->inputs,
                             [&](InputSection *a, InputSection *b) {
                               return isecPriorities[a] > isecPriorities[b];
@@ -362,61 +823,140 @@
   }
 }
 
-void Writer::createOutputSections() {
+static NamePair maybeRenameSection(NamePair key) {
+  auto newNames = config->sectionRenameMap.find(key);
+  if (newNames != config->sectionRenameMap.end())
+    return newNames->second;
+  auto newName = config->segmentRenameMap.find(key.first);
+  if (newName != config->segmentRenameMap.end())
+    return std::make_pair(newName->second, key.second);
+  return key;
+}
+
+template <class LP> void Writer::createOutputSections() {
+  TimeTraceScope timeScope("Create output sections");
   // First, create hidden sections
-  headerSection = make<MachHeaderSection>();
-  bindingSection = make<BindingSection>();
-  lazyBindingSection = make<LazyBindingSection>();
   stringTableSection = make<StringTableSection>();
-  symtabSection = make<SymtabSection>(*stringTableSection);
-  exportSection = make<ExportSection>();
+  symtabSection = makeSymtabSection<LP>(*stringTableSection);
+  indirectSymtabSection = make<IndirectSymtabSection>();
+  if (config->adhocCodesign)
+    codeSignatureSection = make<CodeSignatureSection>();
+  if (config->emitFunctionStarts)
+    functionStartsSection = make<FunctionStartsSection>();
+  if (config->emitBitcodeBundle)
+    make<BitcodeBundleSection>();
 
   switch (config->outputType) {
   case MH_EXECUTE:
     make<PageZeroSection>();
     break;
   case MH_DYLIB:
+  case MH_BUNDLE:
     break;
   default:
     llvm_unreachable("unhandled output file type");
   }
 
-  // Then merge input sections into output sections/segments.
-  for (InputSection *isec : inputSections) {
-    getOrCreateOutputSegment(isec->segname)
-        ->getOrCreateOutputSection(isec->name)
-        ->mergeInput(isec);
+  // 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;
+    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);
+  }
+
+  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);
+    }
   }
 
-  // Remove unneeded segments and sections.
-  // TODO: Avoid creating unneeded segments in the first place
-  for (auto it = outputSegments.begin(); it != outputSegments.end();) {
-    OutputSegment *seg = *it;
-    seg->removeUnneededSections();
-    if (!seg->isNeeded())
-      it = outputSegments.erase(it);
-    else
-      ++it;
+  for (SyntheticSection *ssec : syntheticSections) {
+    auto it = concatOutputSections.find({ssec->segname, ssec->name});
+    if (it == concatOutputSections.end()) {
+      if (ssec->isNeeded())
+        getOrCreateOutputSegment(ssec->segname)->addOutputSection(ssec);
+    } else {
+      error("section from " + toString(it->second->firstSection()->file) +
+            " conflicts with synthetic section " + ssec->segname + "," +
+            ssec->name);
+    }
+  }
+
+  // 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();
+  // Ensure that segments (and the sections they contain) are allocated
+  // addresses in ascending order, which dyld requires.
+  //
+  // Note that at this point, __LINKEDIT sections are empty, but we need to
+  // determine addresses of other segments/sections before generating its
+  // contents.
+  for (OutputSegment *seg : outputSegments) {
+    if (seg == linkEditSegment)
+      continue;
+    assignAddresses(seg);
+    // codesign / libstuff checks for segment ordering by verifying that
+    // `fileOff + fileSize == next segment fileOff`. So we call alignTo() before
+    // (instead of after) computing fileSize to ensure that the segments are
+    // contiguous. We handle addr / vmSize similarly for the same reason.
+    fileOff = alignTo(fileOff, pageSize);
+    addr = alignTo(addr, pageSize);
+    seg->vmSize = addr - seg->firstSection()->addr;
+    seg->fileSize = fileOff - seg->fileOff;
   }
 }
 
+void Writer::finalizeLinkEditSegment() {
+  TimeTraceScope timeScope("Finalize __LINKEDIT segment");
+  // Fill __LINKEDIT contents.
+  std::vector<LinkEditSection *> linkEditSections{
+      in.rebase,  in.binding,    in.weakBinding,        in.lazyBinding,
+      in.exports, symtabSection, indirectSymtabSection, functionStartsSection,
+  };
+  parallelForEach(linkEditSections, [](LinkEditSection *osec) {
+    if (osec)
+      osec->finalizeContents();
+  });
+
+  // Now that __LINKEDIT is filled out, do a proper calculation of its
+  // addresses and offsets.
+  assignAddresses(linkEditSegment);
+  // No need to page-align fileOff / addr here since this is the last segment.
+  linkEditSegment->vmSize = addr - linkEditSegment->firstSection()->addr;
+  linkEditSegment->fileSize = fileOff - linkEditSegment->fileOff;
+}
+
 void Writer::assignAddresses(OutputSegment *seg) {
-  addr = alignTo(addr, PageSize);
-  fileOff = alignTo(fileOff, PageSize);
   seg->fileOff = fileOff;
 
-  for (auto &p : seg->getSections()) {
-    OutputSection *section = p.second;
-    addr = alignTo(addr, section->align);
-    // We must align the file offsets too to avoid misaligned writes of
-    // structs.
-    fileOff = alignTo(fileOff, section->align);
-    section->addr = addr;
-    section->fileOff = fileOff;
-    section->finalize();
+  for (OutputSection *osec : seg->getSections()) {
+    if (!osec->isNeeded())
+      continue;
+    addr = alignTo(addr, osec->align);
+    fileOff = alignTo(fileOff, osec->align);
+    osec->addr = addr;
+    osec->fileOff = isZeroFill(osec->flags) ? 0 : fileOff;
+    osec->finalize();
 
-    addr += section->getSize();
-    fileOff += section->getFileSize();
+    addr += osec->getSize();
+    fileOff += osec->getFileSize();
   }
 }
 
@@ -434,66 +974,87 @@
 
 void Writer::writeSections() {
   uint8_t *buf = buffer->getBufferStart();
-  for (OutputSegment *seg : outputSegments) {
-    for (auto &p : seg->getSections()) {
-      OutputSection *section = p.second;
-      section->writeTo(buf + section->fileOff);
-    }
-  }
+  for (const OutputSegment *seg : outputSegments)
+    for (const OutputSection *osec : seg->getSections())
+      osec->writeTo(buf + osec->fileOff);
 }
 
-void Writer::run() {
-  // dyld requires __LINKEDIT segment to always exist (even if empty).
-  OutputSegment *linkEditSegment =
-      getOrCreateOutputSegment(segment_names::linkEdit);
-
-  scanRelocations();
-  if (in.stubHelper->isNeeded())
-    in.stubHelper->setup();
-
-  // Sort and assign sections to their respective segments. No more sections nor
-  // segments may be created after these methods run.
-  createOutputSections();
-  sortSegmentsAndSections();
-
-  createLoadCommands();
+// In order to utilize multiple cores, we first split the buffer into chunks,
+// compute a hash for each chunk, and then compute a hash value of the hash
+// values.
+void Writer::writeUuid() {
+  TimeTraceScope timeScope("Computing UUID");
+  ArrayRef<uint8_t> data{buffer->getBufferStart(), buffer->getBufferEnd()};
+  unsigned chunkCount = parallel::strategy.compute_thread_count() * 10;
+  // Round-up integer division
+  size_t chunkSize = (data.size() + chunkCount - 1) / chunkCount;
+  std::vector<ArrayRef<uint8_t>> chunks = split(data, chunkSize);
+  std::vector<uint64_t> hashes(chunks.size());
+  parallelForEachN(0, chunks.size(),
+                   [&](size_t i) { hashes[i] = xxHash64(chunks[i]); });
+  uint64_t digest = xxHash64({reinterpret_cast<uint8_t *>(hashes.data()),
+                              hashes.size() * sizeof(uint64_t)});
+  uuidCommand->writeUuid(digest);
+}
 
-  // Ensure that segments (and the sections they contain) are allocated
-  // addresses in ascending order, which dyld requires.
-  //
-  // Note that at this point, __LINKEDIT sections are empty, but we need to
-  // determine addresses of other segments/sections before generating its
-  // contents.
-  for (OutputSegment *seg : outputSegments)
-    if (seg != linkEditSegment)
-      assignAddresses(seg);
+void Writer::writeCodeSignature() {
+  if (codeSignatureSection)
+    codeSignatureSection->writeHashes(buffer->getBufferStart());
+}
 
-  // Fill __LINKEDIT contents.
-  bindingSection->finalizeContents();
-  lazyBindingSection->finalizeContents();
-  exportSection->finalizeContents();
-  symtabSection->finalizeContents();
-
-  // Now that __LINKEDIT is filled out, do a proper calculation of its
-  // addresses and offsets.
-  assignAddresses(linkEditSegment);
-
+void Writer::writeOutputFile() {
+  TimeTraceScope timeScope("Write output file");
   openFile();
   if (errorCount())
     return;
-
   writeSections();
+  writeUuid();
+  writeCodeSignature();
 
   if (auto e = buffer->commit())
     error("failed to write to the output file: " + toString(std::move(e)));
 }
 
-void macho::writeResult() { Writer().run(); }
+template <class LP> void Writer::run() {
+  if (config->entry && !isa<Undefined>(config->entry))
+    prepareBranchTarget(config->entry);
+  scanRelocations();
+  if (in.stubHelper->isNeeded())
+    in.stubHelper->setup();
+  scanSymbols();
+  createOutputSections<LP>();
+  // After this point, we create no new segments; HOWEVER, we might
+  // yet create branch-range extension thunks for architectures whose
+  // hardware call instructions have limited range, e.g., ARM(64).
+  // The thunks are created as InputSections interspersed among
+  // the ordinary __TEXT,_text InputSections.
+  sortSegmentsAndSections();
+  createLoadCommands<LP>();
+  finalizeAddresses();
+  finalizeLinkEditSegment();
+  writeMapFile();
+  writeOutputFile();
+}
+
+template <class LP> void macho::writeResult() { Writer().run<LP>(); }
 
 void macho::createSyntheticSections() {
+  in.header = make<MachHeaderSection>();
+  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>();
   in.stubs = make<StubsSection>();
   in.stubHelper = make<StubHelperSection>();
   in.imageLoaderCache = make<ImageLoaderCacheSection>();
+  in.unwindInfo = makeUnwindInfoSection();
 }
+
+OutputSection *macho::firstTLVDataSection = nullptr;
+
+template void macho::writeResult<LP64>();
+template void macho::writeResult<ILP32>();