[lld-macho] Have dead-stripping work with literal sections

[int3]

Summary

Literal sections are not atomically live or dead. Rather,
liveness is tracked for each individual literal they contain. CStrings
have their liveness tracked via a live bit in StringPiece, and
fixed-width literals have theirs tracked via a BitVector.

The live-marking code now needs to track the offset within each section
that is to be marked live, in order to identify the literal at that
particular offset.

Numbers for linking chromium_framework on my 3.2 GHz 16-Core Intel Xeon W
with both -dead_strip and --deduplicate-literals, with and without this diff
applied:

    N           Min           Max        Median           Avg        Stddev
x  20          4.32          4.44         4.375         4.372    0.03105174
+  20           4.3          4.39          4.36        4.3595   0.023277502
No difference proven at 95.0% confidence

This gives us size savings of about 0.4%.

[int3]

Running some benchmarks locally, will update commit message in a bit

[oontvoo]

lld/MachO/InputSection.h

123

IMHO, 31 is a bit weird. (It's only 1 bit difference!)

[int3]

lld/MachO/InputSection.h

123

1 extra bit here makes the struct take up 1 extra word :)

This was taken from LLD-ELF; I have yet to profile it myself, but it seemed like a reasonable idea

[craig.topper]

lld/MachO/InputSection.h

123

Should live also be uint32_t? If i recall, MSVC needs the types of bitfields to be the same in order to merge the storage.

[tschuett]

lld/MachO/InputSection.h

123

Could you add a static_assert for proof and documentation?

[int3]

lld/MachO/InputSection.h

123

ohh, so that's why LLD-ELF uses a uint32_t. Yeah, I'll add a static_assert.

[int3]

static_assert

[thakis]

Nice!

[lei]

Hi,

The changes in the following commits have been causing failures in our bot, https://lab.llvm.org/buildbot/#/workers/50, since last Friday:

• 464d3dc3d11eec105023011fd41abb1871f46d5d
• 681cfeb59119f2ddc5418e4e3a48c632dcd1aa3e
• 7f2ba39b1688230c663986485f605cf8df90f895
• 5d88f2dd947825750d487f91b3b3735d61f7aa8e
• 5de7467e9821485f492eb97fafd796e1db4c6bb5

All 5 patches seem to be related and pushed at the same time. Please provide a fix to get the bots green or we will have to pull all 5 patches by EOD EDT.

Thank-you

lld/MachO/InputSection.h

 //===- InputSection.h -------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_INPUT_SECTION_H
 #define LLD_MACHO_INPUT_SECTION_H
 
 #include "Config.h"
 #include "Relocations.h"
 
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/BinaryFormat/MachO.h"
 
 namespace lld {
 namespace macho {
 
 class InputFile;
 class OutputSection;
public:
   // 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;
   // Whether the data at \p off in this InputSection is live.
   virtual bool isLive(uint64_t off) const = 0;
+  virtual void markLive(uint64_t off) = 0;
 
   void writeTo(uint8_t *buf);
 
   InputFile *file = nullptr;
   StringRef name;
   StringRef segname;
 
   OutputSection *parent = nullptr;
ConcatInputSection(StringRef segname, StringRef name, InputFile *file,
                      ArrayRef<uint8_t> data, uint32_t align, uint32_t flags)
       : InputSection(ConcatKind, segname, name, file, data, align, flags) {}
 
   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); }
   // ConcatInputSections are entirely live or dead, so the offset is irrelevant.
   bool isLive(uint64_t off) const override { return live; }
+  void markLive(uint64_t off) override { live = true; }
   bool isCoalescedWeak() const { return wasCoalesced && numRefs == 0; }
   bool shouldOmitFromOutput() const { return !live || isCoalescedWeak(); }
 
   static bool classof(const InputSection *isec) {
     return isec->kind() == ConcatKind;
   }
 
   // With subsections_via_symbols, most symbols have their own InputSection,
   // and for weak symbols (e.g. from inline functions), only the
   // InputSection from one translation unit will make it to the output,
   // while all copies in other translation units are coalesced into the
   // first and not copied to the output.
   bool wasCoalesced = false;
   bool live = !config->deadStrip;
   // How many symbols refer to this InputSection.
   uint32_t numRefs = 0;
   uint64_t outSecOff = 0;
   uint64_t outSecFileOff = 0;
 };
 
 // We allocate a lot of these and binary search on them, so they should be as
-// compact as possible. Hence the use of 32 rather than 64 bits for the hash.
+// compact as possible. Hence the use of 31 rather than 64 bits for the hash.
 struct StringPiece {
   // Offset from the start of the containing input section.
   uint32_t inSecOff;
-  uint32_t hash;
+  bool live : 1;
+  uint32_t hash : 31;
   // Offset from the start of the containing output section.
   uint64_t outSecOff;
 
-  StringPiece(uint64_t off, uint32_t hash) : inSecOff(off), hash(hash) {}
+  StringPiece(uint64_t off, uint32_t hash)
+      : inSecOff(off), live(!config->deadStrip), 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(StringRef segname, StringRef name, InputFile *file,
                       ArrayRef<uint8_t> data, uint32_t align, uint32_t flags)
       : InputSection(CStringLiteralKind, segname, name, file, data, align,
                      flags) {}
   uint64_t getFileOffset(uint64_t off) const override;
   uint64_t getOffset(uint64_t off) const override;
-  // FIXME implement this
-  bool isLive(uint64_t off) const override { return true; }
+  bool isLive(uint64_t off) const override { return getStringPiece(off).live; }
+  void markLive(uint64_t off) override { getStringPiece(off).live = true; }
   // Find the StringPiece that contains this offset.
+  StringPiece &getStringPiece(uint64_t off);
   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 {

 
 class WordLiteralInputSection : public InputSection {
 public:
   WordLiteralInputSection(StringRef segname, StringRef name, InputFile *file,
                           ArrayRef<uint8_t> data, uint32_t align,
                           uint32_t flags);
   uint64_t getFileOffset(uint64_t off) const override;
   uint64_t getOffset(uint64_t off) const override;
-  // FIXME implement this
-  bool isLive(uint64_t off) const override { return true; }
+  bool isLive(uint64_t off) const override {
+    return live[off >> power2LiteralSize];
+  }
+  void markLive(uint64_t off) override { live[off >> power2LiteralSize] = 1; }
 
   static bool classof(const InputSection *isec) {
     return isec->kind() == WordLiteralKind;
   }
+
+private:
+  unsigned power2LiteralSize;
+  // The liveness of data[off] is tracked by live[off >> power2LiteralSize].
+  llvm::BitVector live;
 };
 
 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));

lld/MachO/InputSection.cpp

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 {
+StringPiece &CStringInputSection::getStringPiece(uint64_t off) {
   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];
 }
 
+const StringPiece &CStringInputSection::getStringPiece(uint64_t off) const {
+  return const_cast<CStringInputSection *>(this)->getStringPiece(off);
+}
+
 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;
 }
 
 WordLiteralInputSection::WordLiteralInputSection(StringRef segname,
                                                  StringRef name,
                                                  InputFile *file,
                                                  ArrayRef<uint8_t> data,
                                                  uint32_t align, uint32_t flags)
-    : InputSection(WordLiteralKind, segname, name, file, data, align, flags) {}
+    : InputSection(WordLiteralKind, segname, name, file, data, align, flags) {
+  switch (sectionType(flags)) {
+  case S_4BYTE_LITERALS:
+    power2LiteralSize = 2;
+    break;
+  case S_8BYTE_LITERALS:
+    power2LiteralSize = 3;
+    break;
+  case S_16BYTE_LITERALS:
+    power2LiteralSize = 4;
+    break;
+  default:
+    llvm_unreachable("invalid literal section type");
+  }
+
+  live.resize(data.size() >> power2LiteralSize, !config->deadStrip);
+}
 
 uint64_t WordLiteralInputSection::getFileOffset(uint64_t off) const {
   return parent->fileOff + getOffset(off);
 }
 
 uint64_t WordLiteralInputSection::getOffset(uint64_t off) const {
   auto *osec = cast<WordLiteralSection>(parent);
   const uint8_t *buf = data.data();

lld/MachO/MarkLive.cpp

void markLive() {
 
   // We build up a worklist of sections which have been marked as live. We only
   // push into the worklist when we discover an unmarked section, and we mark
   // as we push, so sections never appear twice in the list.
   // Literal sections cannot contain references to other sections, so we only
   // store ConcatInputSections in our worklist.
   SmallVector<ConcatInputSection *, 256> worklist;
 
-  auto enqueue = [&](InputSection *isec) {
+  auto enqueue = [&](InputSection *isec, uint64_t off) {
+    if (isec->isLive(off))
+      return;
+    isec->markLive(off);
     if (auto s = dyn_cast<ConcatInputSection>(isec)) {
       assert(!s->isCoalescedWeak());
-      if (s->live)
-        return;
-      s->live = true;
       worklist.push_back(s);
     }
   };
 
   auto addSym = [&](Symbol *s) {
     s->used = true;
     if (auto *d = dyn_cast<Defined>(s))
       if (d->isec)
-        enqueue(d->isec);
+        enqueue(d->isec, d->value);
   };
 
   // Add GC roots.
   if (config->entry)
     addSym(config->entry);
   for (Symbol *sym : symtab->getSymbols()) {
     if (auto *defined = dyn_cast<Defined>(sym)) {
       // -exported_symbol(s_list)
if (auto *objFile = dyn_cast<ObjFile>(file))
           if (!defined->isExternal() && defined->noDeadStrip)
             addSym(defined);
   if (auto *stubBinder =
           dyn_cast_or_null<DylibSymbol>(symtab->find("dyld_stub_binder")))
     addSym(stubBinder);
   for (InputSection *isec : inputSections) {
     // Sections marked no_dead_strip
     if (isec->flags & S_ATTR_NO_DEAD_STRIP) {
-      enqueue(isec);
+      assert(isa<ConcatInputSection>(isec));
+      enqueue(isec, 0);
       continue;
     }
 
     // mod_init_funcs, mod_term_funcs sections
     if (sectionType(isec->flags) == S_MOD_INIT_FUNC_POINTERS ||
         sectionType(isec->flags) == S_MOD_TERM_FUNC_POINTERS) {
-      enqueue(isec);
+      assert(isa<ConcatInputSection>(isec));
+      enqueue(isec, 0);
       continue;
     }
 
     // Dead strip runs before UnwindInfoSection handling so we need to keep
     // __LD,__compact_unwind alive here.
     // But that section contains absolute references to __TEXT,__text and
     // keeps most code alive due to that. So we can't just enqueue() the
     // section: We must skip the relocations for the functionAddress
if (isec->segname == segment_names::ld &&
         // This is the relocation for the address of the function itself.
         // Ignore it, else these would keep everything alive.
         if (r.offset % compactUnwindEntrySize == 0)
           continue;
 
         if (auto *s = r.referent.dyn_cast<Symbol *>())
           addSym(s);
         else
-          enqueue(r.referent.get<InputSection *>());
+          enqueue(r.referent.get<InputSection *>(), r.addend);
       }
       continue;
     }
   }
 
   do {
     // Mark things reachable from GC roots as live.
     while (!worklist.empty()) {
       ConcatInputSection *s = worklist.pop_back_val();
       assert(s->live && "We mark as live when pushing onto the worklist!");
 
       // Mark all symbols listed in the relocation table for this section.
       for (const Reloc &r : s->relocs) {
         if (auto *s = r.referent.dyn_cast<Symbol *>())
           addSym(s);
         else
-          enqueue(r.referent.get<InputSection *>());
+          enqueue(r.referent.get<InputSection *>(), r.addend);
       }
     }
 
     // S_ATTR_LIVE_SUPPORT sections are live if they point _to_ a live section.
     // Process them in a second pass.
     for (InputSection *isec : inputSections) {
       if (!isa<ConcatInputSection>(isec))
         continue;
       auto concatIsec = cast<ConcatInputSection>(isec);
       // FIXME: Check if copying all S_ATTR_LIVE_SUPPORT sections into a
       // separate vector and only walking that here is faster.
       if (!(concatIsec->flags & S_ATTR_LIVE_SUPPORT) || concatIsec->live)
         continue;
 
       for (const Reloc &r : isec->relocs) {
         bool referentLive;
         if (auto *s = r.referent.dyn_cast<Symbol *>())
           referentLive = s->isLive();
         else
           referentLive = r.referent.get<InputSection *>()->isLive(r.addend);
         if (referentLive)
-          enqueue(isec);
+          enqueue(isec, 0);
       }
     }
 
     // S_ATTR_LIVE_SUPPORT could have marked additional sections live,
     // which in turn could mark additional S_ATTR_LIVE_SUPPORT sections live.
     // Iterate. In practice, the second iteration won't mark additional
     // S_ATTR_LIVE_SUPPORT sections live.
   } while (!worklist.empty());
 }
 
 } // namespace macho
 } // namespace lld

lld/MachO/SyntheticSections.cpp

void CStringSection::addInput(CStringInputSection *isec) {
   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)
+      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.
   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;
     }
   }
 }
 
 // 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) {
   align = 16;
 }
 
 void WordLiteralSection::addInput(WordLiteralInputSection *isec) {
   isec->parent = this;
   // We do all processing of the InputSection here, so it will be effectively
   // finalized.
   isec->isFinal = true;
   const uint8_t *buf = isec->data.data();
   switch (sectionType(isec->flags)) {
   case S_4BYTE_LITERALS: {
-    for (size_t i = 0, e = isec->data.size() / 4; i < e; ++i) {
-      uint32_t value = *reinterpret_cast<const uint32_t *>(buf + i * 4);
+    for (size_t off = 0, e = isec->data.size(); off < e; off += 4) {
+      if (!isec->isLive(off))
+        continue;
+      uint32_t value = *reinterpret_cast<const uint32_t *>(buf + off);
       literal4Map.emplace(value, literal4Map.size());
     }
     break;
   }
   case S_8BYTE_LITERALS: {
-    for (size_t i = 0, e = isec->data.size() / 8; i < e; ++i) {
-      uint64_t value = *reinterpret_cast<const uint64_t *>(buf + i * 8);
+    for (size_t off = 0, e = isec->data.size(); off < e; off += 8) {
+      if (!isec->isLive(off))
+        continue;
+      uint64_t value = *reinterpret_cast<const uint64_t *>(buf + off);
       literal8Map.emplace(value, literal8Map.size());
     }
     break;
   }
   case S_16BYTE_LITERALS: {
-    for (size_t i = 0, e = isec->data.size() / 16; i < e; ++i) {
-      UInt128 value = *reinterpret_cast<const UInt128 *>(buf + i * 16);
+    for (size_t off = 0, e = isec->data.size(); off < e; off += 16) {
+      if (!isec->isLive(off))
+        continue;
+      UInt128 value = *reinterpret_cast<const UInt128 *>(buf + off);
       literal16Map.emplace(value, literal16Map.size());
     }
     break;
   }
   default:
     llvm_unreachable("invalid literal section type");
   }
 }

lld/test/MachO/dead-strip.s

 # RUN: llvm-mc -g -filetype=obj -triple=x86_64-apple-macos \
 # RUN:     %t/debug.s -o %t/debug.o
 # RUN: %lld -lSystem -dead_strip %t/debug.o -o %t/debug
 # RUN: dsymutil -s %t/debug | FileCheck --check-prefix=EXECSTABS %s
 # EXECSTABS-NOT: N_FUN {{.*}} '_unref'
 # EXECSTABS:     N_FUN {{.*}} '_main'
 # EXECSTABS-NOT: N_FUN {{.*}} '_unref'
 
+# RUN: llvm-mc -g -filetype=obj -triple=x86_64-apple-macos \
+# RUN:     %t/literals.s -o %t/literals.o
+# RUN: %lld -dylib -dead_strip --deduplicate-literals %t/literals.o -o %t/literals
+# RUN: llvm-objdump --macho --section="__TEXT,__cstring" --section="__DATA,str_ptrs" \
+# RUN:   --section="__TEXT,__literals" %t/literals | FileCheck %s --check-prefix=LIT
+
+# LIT:      Contents of (__TEXT,__cstring) section
+# LIT-NEXT: foobar
+# LIT-NEXT: Contents of (__DATA,str_ptrs) section
+# LIT-NEXT: __TEXT:__cstring:bar
+# LIT-NEXT: __TEXT:__cstring:bar
+# LIT-NEXT: Contents of (__TEXT,__literals) section
+# LIT-NEXT: ef be ad de {{$}}
+
 #--- basics.s
 .comm _ref_com, 1
 .comm _unref_com, 1
 
 .section __DATA,__unref_section
 _unref_data:
   .quad 4
 

 _unref:
   retq
 
 .globl _main
 _main:
   retq
 
 .subsections_via_symbols
+
+#--- literals.s
+.cstring
+_unref_foo:
+  .ascii "foo"
+_bar:
+Lbar:
+  .asciz "bar"
+_unref_baz:
+  .asciz "baz"
+
+.literal4
+.p2align 2
+L._foo4:
+  .long 0xdeadbeef
+L._bar4:
+  .long 0xdeadbeef
+L._unref:
+  .long 0xfeedface
+
+.section __DATA,str_ptrs,literal_pointers
+.globl _data
+_data:
+  .quad _bar
+  .quad Lbar
+
+## The output binary have these integer literals put into a section that isn't
+## marked with a S_*BYTE_LITERALS flag, so we don't mark word_ptrs with the
+## S_LITERAL_POINTERS flag.
+.section __DATA,word_ptrs
+.globl _more_data
+_more_data:
+  .quad L._foo4
+  .quad L._bar4
+
+.subsections_via_symbols