[LTO] Basic support for internalize.

[davide]

Summary

So, this is still a WIP but I'd like to discuss it to be sure we handle all the cases correctly.

• Similarly to what the gold plugin does, every time we see a new bitcode file we collect the set of the used global variables and for each symbol defined in the bitcode file make a decision to internalize it or not.
• The resolver tells us if a symbol is referenced from outside (this is pretty similar to what the gold linker does during symbol resolution, but they also take in account if a symbol is visible outside, which I plan to implement later). Note, I'm not sure the check added which check the flag is completely correct.
• Once we are done with this step, *in* the combined object, we actually perform the internalize step changing linkage for each GV previously collected.

Some comments:
In gold, the linker tells back to the plugin what's the resolution for a given symbol. WRT internalize, two resolutions are relevant:
-> PREVAILING_DEF_IRONLY (this is the prevailing definition of the symbol, with no references from regular objects)
-> PREVAILING_DEF_IRONLY_EXP (as above, but the symbol is exported to the dynamic symbol table)

We currently cover only the first case properly.

[• rafael]

ELF/LTO.cpp

81

You can leave this for a future patch, no ?

ELF/Symbols.cpp

19 ↗

(On Diff #51471)

dead include.

ELF/Symbols.h

189

Would it be possible to reuse IsUsedInRegularObj for this?

[mehdi_amini]

ELF/LTO.cpp

103

Can't you change the linkage here immediately instead of using s StringSet.

As a side note, I usually not look at lld but in general this code is lacking documentation, if it was in LLVM it would require a lot more.

[ruiu]

ELF/LTO.cpp

100

I don't want to sprinkle FIXMEs to new patches because it wouldn't help readers but instead asking a question to readers. If you are not sure what the correct thing to do but decided to go with some code, then please justify your decision in comment, like

// We are not sure what to do if we are creating a shared object file.
// For now, we do blah blah because blah blah.

132–136

for (const auto &Name : Internalize)
  if (GlobalValue *GV = ...)
    internalize(*GV);

Also, please do not add a blank line at beginning of a function.

ELF/LTO.h

50

StringSet copies strings to its internal buffer. Is this what you want?

"Internalize" is a verb. I think you want to name it a noun.

ELF/SymbolTable.cpp

217

This comment needs to be more descriptive for those who don't understand what is going on in LTO.

[davide]

Addressed comments.

[• rafael]

This looks a lot better.

Testcase? :-)

ELF/LTO.cpp

18

Dead include?

81

This can also go in a future patch, no?

109

ExportDynamic should have the same treatment as shared. Not sure if we already have a convenient predicate for either.

122

You only add symbols that are not internal, I think you can assert this.

133

You can assert GV for now I think.

ELF/SymbolTable.cpp

221

I am not sure just Undefined is sufficient.

If a weak symbol in an object file is replaced with a strong symbol in a .bc file, there can be a reference from the strong symbol to the bit code one.

[davide]

Oh, the testcase was there before (just didn't show up in my last rev, weird).
Addressing some of your comments + reply.

ELF/LTO.cpp

109

Can I do this separately? (And add a specific test for it)

ELF/SymbolTable.cpp

221

Can I do this separately?

[davide]

ELF/SymbolTable.cpp

221

Can we use isUsedInRegularObj or do you prefer me to add a new flag isInRealELF?

[silvas]

ELF/SymbolTable.cpp

221

DefinedElf and UndefinedElf already capture that distinction I think. I don't think a separate flag is necessary.

[grimar]

test/ELF/lto/internalize-basic.ll

4

"-o -" ? That looks a bit wierd to have "-" as a file name IMO, may be just standart temporary file would be better here ?

[davide]

test/ELF/lto/internalize-basic.ll

4

It's stdout.

[silvas]

test/ELF/lto/internalize-basic.ll

4

Doesn't llvm-dis default to stdout? I don't think -o - os needed.

[• rafael]

Please extend the test to coven a symbol that is *not* internalized.

ELF/LTO.cpp

79

This is now unused.

ELF/SymbolTable.cpp

225

So, do you need to set this in here at all?

We already have

if (IsUsedInRegularObj || Other->IsUsedInRegularObj)
  IsUsedInRegularObj = Other->IsUsedInRegularObj = true;

test/ELF/lto/internalize-basic.ll

4

It is not needed if you use it as

llvm-dis < %t2.lto.bc | FileCheck

Which is probably a bit better as llvm-dis doesn't get the filename.

17

What about _start?

[davide]

Address Rafael's comments. Thanks for the review.

[davide]

Remove another dead include.

[• rafael]

ELF/Symbols.h

95

You don't need to change this now.

[davide]

Remove other dead code.

[• rafael]

LGTM

ELF/LTO.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_ELF_LTO_H
 #define LLD_ELF_LTO_H
 
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Linker/IRMover.h"
 
 namespace lld {
 namespace elf {
 
 class BitcodeFile;
 template <class ELFT> class ObjectFile;
 
 class BitcodeCompiler {
 public:
   void add(BitcodeFile &F);
   template <class ELFT> std::unique_ptr<ObjectFile<ELFT>> compile();
 
 private:
   llvm::TargetMachine *getTargetMachine();
 
   llvm::LLVMContext Context;
   llvm::Module Combined{"ld-temp.o", Context};
   llvm::IRMover Mover{Combined};
   SmallString<0> OwningData;
   std::unique_ptr<MemoryBuffer> MB;
+  llvm::StringSet<> InternalizedSyms;
 };
 }
 }
 
 #endif

ELF/LTO.cpp

 #include "LTO.h"
 #include "Config.h"
 #include "Error.h"
 #include "InputFiles.h"
 #include "Symbols.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Bitcode/ReaderWriter.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/Linker/IRMover.h"
 #include "llvm/Support/StringSaver.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
 
 using namespace llvm;
 using namespace llvm::object;
 using namespace llvm::ELF;
 
 using namespace lld;
 using namespace lld::elf;
 

 
 void BitcodeCompiler::add(BitcodeFile &F) {
   std::unique_ptr<IRObjectFile> Obj =
       check(IRObjectFile::create(F.MB, Context));
   std::vector<GlobalValue *> Keep;
   unsigned BodyIndex = 0;
   ArrayRef<SymbolBody *> Bodies = F.getSymbols();
 
+  SmallPtrSet<GlobalValue *, 8> Used;
   for (const BasicSymbolRef &Sym : Obj->symbols()) {
     GlobalValue *GV = Obj->getSymbolGV(Sym.getRawDataRefImpl());
     assert(GV);
     if (GV->hasAppendingLinkage()) {
       Keep.push_back(GV);
       continue;
     }
     if (!BitcodeFile::shouldSkip(Sym)) {
       if (SymbolBody *B = Bodies[BodyIndex++])
         if (&B->repl() == B && isa<DefinedBitcode>(B)) {
           switch (GV->getLinkage()) {
           default:
             break;
           case llvm::GlobalValue::LinkOnceAnyLinkage:
             GV->setLinkage(GlobalValue::WeakAnyLinkage);
             break;
           case llvm::GlobalValue::LinkOnceODRLinkage:
             GV->setLinkage(GlobalValue::WeakODRLinkage);
             break;
           }
+          // We collect the set of symbols we want to internalize here
+          // and change the linkage after the IRMover executed, i.e. after
+          // we imported the symbols and satisfied undefined references
+          // to it. We can't just change linkage here because otherwise
+          // the IRMover will just rename the symbol.
+
+          // Shared libraries need to be handled slightly differently.
+          // For now, let's be conservative and just never internalize
+          // symbols when creating a shared library.
+          if (!Config->Shared && !Used.count(GV) && !B->isUsedInRegularObj())
+            InternalizedSyms.insert(GV->getName());
+
           Keep.push_back(GV);
         }
     }
   }
 
   Mover.move(Obj->takeModule(), Keep,
              [](GlobalValue &, IRMover::ValueAdder) {});
 }
 
+static void internalize(GlobalValue &GV) {
+  assert(!GV.hasLocalLinkage() &&
+      "Trying to internalize a symbol with local linkage!") ;
+  GV.setLinkage(GlobalValue::InternalLinkage);
+}
+
 // Merge all the bitcode files we have seen, codegen the result
 // and return the resulting ObjectFile.
 template <class ELFT>
 std::unique_ptr<elf::ObjectFile<ELFT>> BitcodeCompiler::compile() {
+  for (const auto &Name : InternalizedSyms) {
+    GlobalValue *GV = Combined.getNamedValue(Name.first());
+    assert(GV);
+    internalize(*GV);
+  }
+
   if (Config->SaveTemps)
     saveBCFile(Combined, ".lto.bc");
 
   std::unique_ptr<TargetMachine> TM(getTargetMachine());
   runLTOPasses(Combined, *TM);
 
   raw_svector_ostream OS(OwningData);
   legacy::PassManager CodeGenPasses;

ELF/SymbolTable.cpp

 // the same name. Decisions are made based on symbol type.
 template <class ELFT> void SymbolTable<ELFT>::resolve(SymbolBody *New) {
   Symbol *Sym = insert(New);
   if (Sym->Body == New)
     return;
 
   SymbolBody *Existing = Sym->Body;
 
+  // We want to internalize symbols for LTO to be effective,
+  // but we can internalize only those that are not referenced
+  // from regular objects.
+  if (auto *BC = dyn_cast<DefinedBitcode>(Existing))
+    if (auto *U = dyn_cast<Undefined>(New))
+      BC->setUsedInRegularObj();
+  if (auto *U = dyn_cast<Undefined>(Existing))
+    if (auto *BC = dyn_cast<DefinedBitcode>(New))
+      BC->setUsedInRegularObj();
+
   if (Lazy *L = dyn_cast<Lazy>(Existing)) {
     if (auto *Undef = dyn_cast<Undefined>(New)) {
       addMemberFile(Undef, L);
       return;
     }
     // Found a definition for something also in an archive.
     // Ignore the archive definition.
     Sym->Body = New;

ELF/Symbols.h

public:
   uint32_t PltIndex = -1;
   bool hasGlobalDynIndex() { return GlobalDynIndex != uint32_t(-1); }
   bool isInGot() const { return GotIndex != -1U; }
   bool isInPlt() const { return PltIndex != -1U; }
 
   template <class ELFT>
   typename ELFT::uint getVA(typename ELFT::uint Addend = 0) const;
 
+  void setUsedInRegularObj() { IsUsedInRegularObj = true; }
+
   template <class ELFT> typename ELFT::uint getGotVA() const;
   template <class ELFT> typename ELFT::uint getGotPltVA() const;
   template <class ELFT> typename ELFT::uint getPltVA() const;
   template <class ELFT> typename ELFT::uint getSize() const;
 
   // A SymbolBody has a backreference to a Symbol. Originally they are
   // doubly-linked. A backreference will never change. But the pointer
   // in the Symbol may be mutated by the resolver. If you have a

 protected:
   SymbolBody(Kind K, StringRef Name, bool IsWeak, bool IsLocal,
              uint8_t Visibility, uint8_t Type)
       : SymbolKind(K), IsWeak(IsWeak), IsLocal(IsLocal), Visibility(Visibility),
         MustBeInDynSym(false), NeedsCopyOrPltAddr(false), Name(Name) {
     IsFunc = Type == llvm::ELF::STT_FUNC;
     IsTls = Type == llvm::ELF::STT_TLS;
     IsGnuIFunc = Type == llvm::ELF::STT_GNU_IFUNC;
-    IsUsedInRegularObj = K != SharedKind && K != LazyKind;
+    IsUsedInRegularObj =
+        K != SharedKind && K != LazyKind && K != DefinedBitcodeKind;
   }
 
   const unsigned SymbolKind : 8;
   unsigned IsWeak : 1;
   unsigned IsLocal : 1;
   unsigned Visibility : 2;
 
   // True if the symbol was used for linking and thus need to be

 };
 
 class DefinedBitcode : public Defined {
 public:
   DefinedBitcode(StringRef Name, bool IsWeak, uint8_t Visibility);
   static bool classof(const SymbolBody *S);
 };
 
 class DefinedCommon : public Defined {
 public:
   DefinedCommon(StringRef N, uint64_t Size, uint64_t Alignment, bool IsWeak,
                 uint8_t Visibility);
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::DefinedCommonKind;
   }
 
public:
 
   static bool classof(const SymbolBody *S) { return S->kind() == LazyKind; }
 
   // Returns an object file for this symbol, or a nullptr if the file
   // was already returned.
   std::unique_ptr<InputFile> getMember();
 
   void setWeak() { IsWeak = true; }
-  void setUsedInRegularObj() { IsUsedInRegularObj = true; }
 
 private:
   ArchiveFile *File;
   const llvm::object::Archive::Symbol Sym;
 };
 
 // Some linker-generated symbols need to be created as
 // DefinedRegular symbols, so they need Elf_Sym symbols.

test/ELF/lto/internalize-basic.ll

+; REQUIRES: x86
+; RUN: llvm-as %s -o %t.o
+; RUN: ld.lld -m elf_x86_64 %t.o -o %t2 -save-temps
+; RUN: llvm-dis %t2.lto.bc -o - | FileCheck %s
+
+target triple = "x86_64-unknown-linux-gnu"
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @_start() {
+  ret void
+}
+
+define hidden void @foo() {
+  ret void
+}
+
+; Check that foo function is correctly internalized.
+; CHECK: define internal void @foo()