[not for review][lld-macho] Preserve skew + alignment for individual cstrings

[int3]

Summary

When deduplicating cstrings, pick the alignment/skew of the one with the
greater alignment. If they have the same alignment, pick the one earlier
on the command line.

This doesn't actually work, just a PoC for future reference.

lld/MachO/InputSection.cpp

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)));
+    // fprintf(stderr, "%llx %s\n", off, s.substr(0, size));
     s = s.substr(size);
     off += size;
   }
 }
 
 StringPiece &CStringInputSection::getStringPiece(uint64_t off) {
   if (off >= data.size())
     fatal(toString(this) + ": offset is outside the section");

lld/MachO/SyntheticSections.h

 
 #include "Config.h"
 #include "ExportTrie.h"
 #include "InputSection.h"
 #include "OutputSection.h"
 #include "OutputSegment.h"
 #include "Target.h"
 
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/MC/StringTableBuilder.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <unordered_map>
 
private:
   llvm::SmallString<261> xarPath;
   uint64_t xarSize;
 };
 
 class CStringSection final : public SyntheticSection {
 public:
   CStringSection();
   void addInput(CStringInputSection *);
-  uint64_t getSize() const override { return builder.getSize(); }
+  uint64_t getSize() const override { return size; }
   void finalizeContents();
   bool isNeeded() const override { return !inputs.empty(); }
-  void writeTo(uint8_t *buf) const override { builder.write(buf); }
+  void writeTo(uint8_t *buf) const override;
 
   std::vector<CStringInputSection *> inputs;
 
 private:
-  llvm::StringTableBuilder builder;
+  llvm::DenseMap<llvm::CachedHashStringRef, uint64_t> stringIndexMap;
+  size_t size = 0;
 };
 
 class CFStringSection final : public SyntheticSection {
 public:
   CFStringSection();
   void addInput(CFStringInputSection *);
   uint64_t getSize() const override { return 0; }
   void finalizeContents();

lld/MachO/SyntheticSections.cpp

 // are all accessed by x86_64 SIMD operations -- x86_64 requires SIMD accesses
 // to be 16-byte-aligned. So for now, I'm 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.
 CStringSection::CStringSection()
-    : SyntheticSection(segment_names::text, section_names::cString),
-      builder(StringTableBuilder::RAW,
-              /*Alignment=*/target->cpuType == CPU_TYPE_X86_64 ? 16 : 1) {
-  align = target->cpuType == CPU_TYPE_X86_64 ? 16 : 1;
+    : SyntheticSection(segment_names::text, section_names::cString) {
   flags = S_CSTRING_LITERALS;
 }
 
 void CStringSection::addInput(CStringInputSection *isec) {
   isec->parent = this;
+  align = std::max(align, isec->align);
   inputs.push_back(isec);
 }
 
 void CStringSection::finalizeContents() {
-  // 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)
-      if (isec->pieces[i].live)
-        builder.add(isec->getCachedHashStringRef(i));
-
-  // Fix the string table content. After this, the contents will never change.
-  builder.finalizeInOrder();
-
-  // finalize() fixed tail-optimized strings, so we can now get
-  // offsets of strings. Get an offset for each string and save it
-  // to a corresponding SectionPiece for easy access.
+  llvm::stable_sort(inputs, [](InputSection *a, InputSection *b) {
+    return a->align > b->align;
+  });
+  for (const CStringInputSection *isec : inputs) {
+    for (size_t i = 0, e = isec->pieces.size(); i != e; ++i) {
+      if (isec->pieces[i].live) {
+        auto s = isec->getCachedHashStringRef(i);
+        auto it = stringIndexMap.insert(std::make_pair(s, 0));
+        if (it.second) {
+          uint64_t skew = isec->pieces[i].inSecOff % isec->align;
+          size_t start = alignTo(size, isec->align, skew);
+          // fprintf(stderr, "%llx %llx %llx %llx %s\n",
+          // isec->pieces[i].inSecOff, start, skew, isec->align, s.data());
+          it.first->second = start;
+          size = start + s.size();
+        }
+      }
+    }
+  }
+
+  // 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) {
       if (!isec->pieces[i].live)
         continue;
       isec->pieces[i].outSecOff =
-          builder.getOffset(isec->getCachedHashStringRef(i));
-      isec->isFinal = true;
-    }
-  }
+          stringIndexMap.lookup(isec->getCachedHashStringRef(i));
+    }
+
+void CStringSection::writeTo(uint8_t *buf) const {
+  for (const auto &p : stringIndexMap) {
+    StringRef data = p.first.val();
+    uint64_t off = p.second;
+    if (!data.empty())
+      memcpy(buf + off, data.data(), data.size());
+  }
 }
 
 // This section is actually emitted as __TEXT,__const by ld64, but clang may
 // emit input sections of that name, and LLD doesn't currently support mixing
 // synthetic and concat-type OutputSections. To work around this, I've given
 // our merged-literals section a different name.
 WordLiteralSection::WordLiteralSection()
     : SyntheticSection(segment_names::text, section_names::literals) {