[lld-macho] LTO: Unset VisibleToRegularObj where possible

[int3]

Summary

This allows LLVM's LTO to internalize symbols that are not referenced
directly by regular objects. Naturally, this means we need to track
which symbols are referenced by regular objects. The approach taken here
is similar to LLD-COFF's: like the COFF port, we extend
SymbolTable::insert() to set the isVisibleToRegularObj bit. (LLD-ELF
relies on the Symbol constructor and Symbol::mergeProperties(), but
the Mach-O port does not have a mergeProperties() equivalent.)

From what I can tell, ld64 (which uses libLTO) doesn't do this
optimization at all. I'm not even sure libLTO provides a way to do this.
Not having ld64's behavior as a reference implementation is unfortunate;
instead, I am relying on LLD-ELF/COFF's behavior as references while
erring on the conservative side. In particular, LLD-MachO will only do
this optimization for executables right now.

We also don't attempt it when -flat_namespace is used -- otherwise
we'd need scan the symbol table to find matches for every un-namespaced
symbol reference, which is expensive.

internalize.ll is based off the LLD-ELF tests internalize-basic.ll and
internalize-undef.ll. Looks like @davide added some of LLD-ELF's internalize
tests, so adding him as a reviewer...

[int3]

lld/MachO/LTO.cpp

41–43

this allows us to access the *.internalize.bc files in our test

[davide]

removing davide
+ steven

[int3]

update

[int3]

remove stray change

[gkm]

LGTM

lld/MachO/Symbols.h

98

Why the bitfield width here? Do we anticipate adding more flags?

[int3]

lld/MachO/Symbols.h

98

LLD-ELF does have a bunch more flags, I haven't totally vetted them yet to determine if we'll need them. I guess we can skip the bitfield width for now.

lld/MachO/LTO.cpp

 #include "llvm/Support/FileSystem.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/ObjCARC.h"
 
 using namespace lld;
 using namespace lld::macho;
 using namespace llvm;
+using namespace llvm::MachO;
 using namespace llvm::sys;
 
 static lto::Config createConfig() {
   lto::Config c;
   c.Options = initTargetOptionsFromCodeGenFlags();
   c.CodeModel = getCodeModelFromCMModel();
   c.CPU = getCPUStr();
   c.MAttrs = getMAttrs();
   c.UseNewPM = config->ltoNewPassManager;
   c.PreCodeGenPassesHook = [](legacy::PassManager &pm) {
     pm.add(createObjCARCContractPass());
   };
   c.TimeTraceEnabled = config->timeTraceEnabled;
   c.TimeTraceGranularity = config->timeTraceGranularity;
+  if (config->saveTemps)
+    checkError(c.addSaveTemps(config->outputFile.str() + ".",
+                              /*UseInputModulePath=*/true));
   return c;
 }
 
 BitcodeCompiler::BitcodeCompiler() {
   lto::ThinBackend backend = lto::createInProcessThinBackend(
       heavyweight_hardware_concurrency(config->thinLTOJobs));
   ltoObj = std::make_unique<lto::LTO>(createConfig(), backend);
 }
for (const lto::InputFile::Symbol &objSym : objSyms) {
 
     // Ideally we shouldn't check for SF_Undefined but currently IRObjectFile
     // reports two symbols for module ASM defined. Without this check, lld
     // flags an undefined in IR with a definition in ASM as prevailing.
     // Once IRObjectFile is fixed to report only one symbol this hack can
     // be removed.
     r.Prevailing = !objSym.isUndefined() && sym->getFile() == &f;
 
+    // FIXME: What about other output types? And we can probably be less
+    // restrictive with -flat_namespace, but it's an infrequent use case.
+    r.VisibleToRegularObj = config->outputType != MH_EXECUTE ||
+                            config->namespaceKind == NamespaceKind::flat ||
+                            sym->isUsedInRegularObj;
+
     // Un-define the symbol so that we don't get duplicate symbol errors when we
     // load the ObjFile emitted by LTO compilation.
     if (r.Prevailing)
       replaceSymbol<Undefined>(sym, sym->getName(), sym->getFile(),
                                RefState::Strong);
 
     // TODO: set the other resolution configs properly
-    r.VisibleToRegularObj = true;
   }
   checkError(ltoObj->add(std::move(f.obj), resols));
 }
 
 // Merge all the bitcode files we have seen, codegen the result
 // and return the resulting ObjectFile(s).
 std::vector<ObjFile *> BitcodeCompiler::compile() {
   unsigned maxTasks = ltoObj->getMaxTasks();

lld/MachO/SymbolTable.h

public:
   Defined *addSynthetic(StringRef name, InputSection *, uint64_t value,
                         bool isPrivateExtern, bool includeInSymtab);
 
   ArrayRef<Symbol *> getSymbols() const { return symVector; }
   Symbol *find(llvm::CachedHashStringRef name);
   Symbol *find(StringRef name) { return find(llvm::CachedHashStringRef(name)); }
 
 private:
-  std::pair<Symbol *, bool> insert(StringRef name);
+  std::pair<Symbol *, bool> insert(StringRef name, const InputFile *);
   llvm::DenseMap<llvm::CachedHashStringRef, int> symMap;
   std::vector<Symbol *> symVector;
 };
 
 void treatUndefinedSymbol(const Undefined &);
 
 extern SymbolTable *symtab;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/SymbolTable.cpp

 
 Symbol *SymbolTable::find(CachedHashStringRef cachedName) {
   auto it = symMap.find(cachedName);
   if (it == symMap.end())
     return nullptr;
   return symVector[it->second];
 }
 
-std::pair<Symbol *, bool> SymbolTable::insert(StringRef name) {
+std::pair<Symbol *, bool> SymbolTable::insert(StringRef name,
+                                              const InputFile *file) {
   auto p = symMap.insert({CachedHashStringRef(name), (int)symVector.size()});
 
+  Symbol *sym;
+  if (!p.second) {
     // Name already present in the symbol table.
-  if (!p.second)
-    return {symVector[p.first->second], false};
-
+    sym = symVector[p.first->second];
+  } else {
     // Name is a new symbol.
-  Symbol *sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
+    sym = reinterpret_cast<Symbol *>(make<SymbolUnion>());
     symVector.push_back(sym);
-  return {sym, true};
+  }
+
+  sym->isUsedInRegularObj |= !file || isa<ObjFile>(file);
+  return {sym, p.second};
 }
 
 Defined *SymbolTable::addDefined(StringRef name, InputFile *file,
                                  InputSection *isec, uint64_t value,
                                  uint64_t size, bool isWeakDef,
                                  bool isPrivateExtern) {
   Symbol *s;
   bool wasInserted;
   bool overridesWeakDef = false;
-  std::tie(s, wasInserted) = insert(name);
+  std::tie(s, wasInserted) = insert(name, file);
 
   if (!wasInserted) {
     if (auto *defined = dyn_cast<Defined>(s)) {
       if (isWeakDef) {
         // Both old and new symbol weak (e.g. inline function in two TUs):
         // If one of them isn't private extern, the merged symbol isn't.
         if (defined->isWeakDef())
           defined->privateExtern &= isPrivateExtern;
Defined *SymbolTable::addDefined(StringRef name, InputFile *file,
   defined->overridesWeakDef = overridesWeakDef;
   return defined;
 }
 
 Symbol *SymbolTable::addUndefined(StringRef name, InputFile *file,
                                   bool isWeakRef) {
   Symbol *s;
   bool wasInserted;
-  std::tie(s, wasInserted) = insert(name);
+  std::tie(s, wasInserted) = insert(name, file);
 
   RefState refState = isWeakRef ? RefState::Weak : RefState::Strong;
 
   if (wasInserted)
     replaceSymbol<Undefined>(s, name, file, refState);
   else if (auto *lazy = dyn_cast<LazySymbol>(s))
     lazy->fetchArchiveMember();
   else if (auto *dynsym = dyn_cast<DylibSymbol>(s))
     dynsym->refState = std::max(dynsym->refState, refState);
   else if (auto *undefined = dyn_cast<Undefined>(s))
     undefined->refState = std::max(undefined->refState, refState);
   return s;
 }
 
 Symbol *SymbolTable::addCommon(StringRef name, InputFile *file, uint64_t size,
                                uint32_t align, bool isPrivateExtern) {
   Symbol *s;
   bool wasInserted;
-  std::tie(s, wasInserted) = insert(name);
+  std::tie(s, wasInserted) = insert(name, file);
 
   if (!wasInserted) {
     if (auto *common = dyn_cast<CommonSymbol>(s)) {
       if (size < common->size)
         return s;
     } else if (isa<Defined>(s)) {
       return s;
     }
     // Common symbols take priority over all non-Defined symbols, so in case of
     // a name conflict, we fall through to the replaceSymbol() call below.
   }
 
   replaceSymbol<CommonSymbol>(s, name, file, size, align, isPrivateExtern);
   return s;
 }
 
 Symbol *SymbolTable::addDylib(StringRef name, DylibFile *file, bool isWeakDef,
                               bool isTlv) {
   Symbol *s;
   bool wasInserted;
-  std::tie(s, wasInserted) = insert(name);
+  std::tie(s, wasInserted) = insert(name, file);
 
   RefState refState = RefState::Unreferenced;
   if (!wasInserted) {
     if (auto *defined = dyn_cast<Defined>(s)) {
       if (isWeakDef && !defined->isWeakDef())
         defined->overridesWeakDef = true;
     } else if (auto *undefined = dyn_cast<Undefined>(s)) {
       refState = undefined->refState;

 Symbol *SymbolTable::addDynamicLookup(StringRef name) {
   return addDylib(name, /*file=*/nullptr, /*isWeakDef=*/false, /*isTlv=*/false);
 }
 
 Symbol *SymbolTable::addLazy(StringRef name, ArchiveFile *file,
                              const object::Archive::Symbol &sym) {
   Symbol *s;
   bool wasInserted;
-  std::tie(s, wasInserted) = insert(name);
+  std::tie(s, wasInserted) = insert(name, file);
 
   if (wasInserted)
     replaceSymbol<LazySymbol>(s, file, sym);
   else if (isa<Undefined>(s) || (isa<DylibSymbol>(s) && s->isWeakDef()))
     file->fetch(sym);
   return s;
 }
 

lld/MachO/Symbols.h

public:
   uint32_t stubsIndex = UINT32_MAX;
 
   uint32_t symtabIndex = UINT32_MAX;
 
   InputFile *getFile() const { return file; }
 
 protected:
   Symbol(Kind k, StringRefZ name, InputFile *file)
-      : symbolKind(k), nameData(name.data), nameSize(name.size), file(file) {}
+      : symbolKind(k), nameData(name.data), nameSize(name.size), file(file),
+        isUsedInRegularObj(!file || isa<ObjFile>(file)) {}
 
   Kind symbolKind;
   const char *nameData;
   mutable uint32_t nameSize;
   InputFile *file;
+
+public:
+  // True if this symbol was referenced by a regular (non-bitcode) object.
+  bool isUsedInRegularObj;
 };
 
 class Defined : public Symbol {
 public:
   Defined(StringRefZ name, InputFile *file, InputSection *isec, uint64_t value,
           uint64_t size, bool isWeakDef, bool isExternal, bool isPrivateExtern)
       : Symbol(DefinedKind, name, file), isec(isec), value(value), size(size),
         overridesWeakDef(false), privateExtern(isPrivateExtern),

 template <typename T, typename... ArgT>
 T *replaceSymbol(Symbol *s, ArgT &&...arg) {
   static_assert(sizeof(T) <= sizeof(SymbolUnion), "SymbolUnion too small");
   static_assert(alignof(T) <= alignof(SymbolUnion),
                 "SymbolUnion not aligned enough");
   assert(static_cast<Symbol *>(static_cast<T *>(nullptr)) == nullptr &&
          "Not a Symbol");
 
-  return new (s) T(std::forward<ArgT>(arg)...);
+  bool isUsedInRegularObj = s->isUsedInRegularObj;
+  T *sym = new (s) T(std::forward<ArgT>(arg)...);
+  sym->isUsedInRegularObj |= isUsedInRegularObj;
+  return sym;
 }
 
 } // namespace macho
 
 std::string toString(const macho::Symbol &);
 std::string toMachOString(const llvm::object::Archive::Symbol &);
 
 } // namespace lld
 
 #endif

lld/test/MachO/internalize.ll

+; REQUIRES: x86
+
+;; Check that we internalize bitcode symbols (only) where possible, i.e. when
+;; they are not referenced by undefined symbols originating from non-bitcode
+;; files.
+
+; RUN: rm -rf %t; split-file %s %t
+; RUN: llvm-as %t/test.s -o %t/test.o
+; RUN: llvm-as %t/baz.s -o %t/baz.o
+; RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %t/regular.s -o %t/regular.o
+; RUN: %lld -pie -lSystem %t/test.o %t/baz.o %t/regular.o -o %t/test -save-temps
+; RUN: llvm-dis < %t/test.0.2.internalize.bc | FileCheck %s
+; RUN: llvm-objdump --macho --syms %t/test | FileCheck %s --check-prefix=SYMTAB
+
+;; Check that main is not internalized. This covers the case of bitcode symbols
+;; referenced by undefined symbols that don't belong to any InputFile.
+; CHECK: define void @main()
+
+;; Check that the foo and bar functions are correctly internalized.
+; CHECK: define internal void @bar()
+; CHECK: define internal void @foo()
+
+;; Check that a bitcode symbol that is referenced by a regular object file isn't
+;; internalized.
+; CHECK: define void @used_in_regular_obj()
+
+;; Check that a bitcode symbol that is defined in another bitcode file gets
+;; internalized.
+; CHECK: define internal void @baz()
+
+; Check foo and bar are not emitted to the .symtab
+; SYMTAB-LABEL: SYMBOL TABLE:
+; SYMTAB-NEXT:  g     F __TEXT,__text _main
+; SYMTAB-NEXT:  g     F __TEXT,__text _used_in_regular_obj
+; SYMTAB-NEXT:  g     F __TEXT,__text __mh_execute_header
+; SYMTAB-EMPTY:
+
+;--- test.s
+target triple = "x86_64-apple-macosx10.15.0"
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+declare void @baz()
+
+define void @main() {
+  call void @bar()
+  call void @baz()
+  ret void
+}
+
+define void @bar() {
+  ret void
+}
+
+define hidden void @foo() {
+  ret void
+}
+
+define void @used_in_regular_obj() {
+  ret void
+}
+
+;--- baz.s
+target triple = "x86_64-apple-macosx10.15.0"
+target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @baz() {
+  ret void
+}
+
+;--- regular.s
+.data
+.quad _used_in_regular_obj

lld/test/MachO/lto-save-temps.ll

 ; REQUIRES: x86
 
 ; Test that we compile regular LTO inputs in a single task but handle ThinLTO
 ; modules in separate tasks.
 
 ; RUN: rm -rf %t; split-file %s %t
 ; RUN: llvm-as %t/foo.ll -o %t/foo.o
-; RUN: llvm-as %t/test.ll -o %t/test.o
-; RUN: %lld -save-temps %t/foo.o %t/test.o -o %t/test
+; RUN: llvm-as %t/bar.ll -o %t/bar.o
+; RUN: %lld -dylib -save-temps %t/foo.o %t/bar.o -o %t/test
 ; RUN: llvm-objdump -d --no-show-raw-insn %t/test.lto.o | FileCheck %s --check-prefix=ALL
 ; RUN: llvm-objdump -d --no-show-raw-insn %t/test | FileCheck %s --check-prefix=ALL
 
 ; RUN: rm -rf %t; split-file %s %t
 ; RUN: opt -module-summary %t/foo.ll -o %t/foo.o
-; RUN: opt -module-summary %t/test.ll -o %t/test.o
-; RUN: %lld -save-temps %t/foo.o %t/test.o -o %t/test
+; RUN: opt -module-summary %t/bar.ll -o %t/bar.o
+; RUN: %lld -dylib -save-temps %t/foo.o %t/bar.o -o %t/test
 ; RUN: llvm-objdump -d --no-show-raw-insn %t/test1.lto.o | FileCheck %s --check-prefix=FOO
 ; RUN: llvm-objdump -d --no-show-raw-insn %t/test2.lto.o | FileCheck %s --check-prefix=MAIN
 ; RUN: llvm-objdump -d --no-show-raw-insn %t/test | FileCheck %s --check-prefix=ALL
 
 ; FOO:      <_foo>:
 ; FOO-NEXT: retq
 
-; MAIN:      <_main>:
+; MAIN:      <_bar>:
 ; MAIN-NEXT: retq
 
 ; ALL:      <_foo>:
 ; ALL-NEXT: retq
-; ALL:      <_main>:
+; ALL:      <_bar>:
 ; ALL-NEXT: retq
 
 ;--- foo.ll
 
 target triple = "x86_64-apple-macosx10.15.0"
 target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @foo() {
   ret void
 }
 
-;--- test.ll
+;--- bar.ll
 
 target triple = "x86_64-apple-macosx10.15.0"
 target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
-define void @main() {
+define void @bar() {
   ret void
 }