Add an internalization step to the ThinLTOCodeGenerator

[mehdi_amini]

Summary

keeping as much as possible internal/private is
known to help the optimizer. Let's try to benefit from
this in ThinLTO.
Note: this is early work, but is enough to build clang (and
all the LLVM tools). I still need to write some lit-tests...

[mehdi_amini]

Rebase

[mehdi_amini]

Rebase

[mehdi_amini]

Add a test

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

309

It seems there is already some support in libLTO for detecting these, see the call to LTOModule::addAsmGlobalSymbolUndef(). Can that be leveraged here? What is the difference between what is being detected by these two cases?

If it needs to use the IRObject method, can that functionality be refactored into a method in libObject that is callable from here? It seems like it could return the AsmSymbols vector and you could just iterate that here looking for a Key that is BasicSymbolRef::SF_Undefined in the returned pair, and is !TheModule.getNamedValue(Key). Using a refactored common routine would make it easier to do similar optimizations in the gold and lld cases as well.

378

Missing comment

386

I guess the assumption is that there is nothing to export if there is nothing to preserve? Should there be an assertion here that ExportList is empty?

406

doxygen style /// comment (here and with other added functions)

420

Why not add these to the PreservedGV set?

671

Should this be a FIXME?

[mehdi_amini]

Address comments

lib/LTO/ThinLTOCodeGenerator.cpp

386

No this is completely independent: if the client didn't supply anything to preserve, we don't internalize at all. Changed the comment.

406

I think it is relevant only for public API. These are static function so they won't show up in doxygen: http://llvm.org/doxygen/ThinLTOCodeGenerator_8cpp.html

420

PreservedGV drives the internalizer, this is possibly driving other places in LLVM I think, like GlobalDCE for example.

671

added

[mehdi_amini]

r267317

include/llvm/Object/RecordStreamer.h

 //===-- RecordStreamer.h - Record asm defined and used symbols ---*- C++ -*===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_LIB_OBJECT_RECORDSTREAMER_H
 #define LLVM_LIB_OBJECT_RECORDSTREAMER_H
 
 #include "llvm/MC/MCStreamer.h"
 
 namespace llvm {
 class RecordStreamer : public MCStreamer {
 public:
   enum State { NeverSeen, Global, Defined, DefinedGlobal, Used };
 
 private:
   StringMap<State> Symbols;
   void markDefined(const MCSymbol &Symbol);
   void markGlobal(const MCSymbol &Symbol);
   void markUsed(const MCSymbol &Symbol);
   void visitUsedSymbol(const MCSymbol &Sym) override;
 
 public:
   typedef StringMap<State>::const_iterator const_iterator;
   const_iterator begin();
   const_iterator end();
   RecordStreamer(MCContext &Context);
   void EmitInstruction(const MCInst &Inst, const MCSubtargetInfo &STI) override;
   void EmitLabel(MCSymbol *Symbol) override;
   void EmitAssignment(MCSymbol *Symbol, const MCExpr *Value) override;
   bool EmitSymbolAttribute(MCSymbol *Symbol, MCSymbolAttr Attribute) override;
   void EmitZerofill(MCSection *Section, MCSymbol *Symbol, uint64_t Size,
                     unsigned ByteAlignment) override;
   void EmitCommonSymbol(MCSymbol *Symbol, uint64_t Size,
                         unsigned ByteAlignment) override;
 };
 }
 #endif

lib/LTO/ThinLTOCodeGenerator.cpp

 // This file implements the Thin Link Time Optimization library. This library is
 // intended to be used by linker to optimize code at link time.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/LTO/ThinLTOCodeGenerator.h"
 #include "LLVMLTORevision.h"
 
+#include "UpdateCompilerUsed.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/Analysis/ModuleSummaryAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Bitcode/BitcodeWriterPass.h"
 #include "llvm/Bitcode/ReaderWriter.h"
 #include "llvm/ExecutionEngine/ObjectMemoryBuffer.h"
 #include "llvm/IR/DiagnosticPrinter.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/Mangler.h"
 #include "llvm/IRReader/IRReader.h"
 #include "llvm/Linker/Linker.h"
+#include "llvm/MC/MCAsmInfo.h"
+#include "llvm/MC/MCContext.h"
+#include "llvm/MC/MCInstrInfo.h"
+#include "llvm/MC/MCObjectFileInfo.h"
+#include "llvm/MC/MCParser/MCAsmParser.h"
+#include "llvm/MC/MCParser/MCTargetAsmParser.h"
+#include "llvm/MC/MCRegisterInfo.h"
 #include "llvm/MC/SubtargetFeature.h"
 #include "llvm/Object/ModuleSummaryIndexObjectFile.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/CachePruning.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/SHA1.h"
+#include "llvm/Object/RecordStreamer.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/ThreadPool.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/FunctionImport.h"
+#include "llvm/Transforms/IPO/Internalize.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/ObjCARC.h"
 #include "llvm/Transforms/Utils/FunctionImportUtils.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "thinlto"
 
static void optimizeModule(Module &TheModule, TargetMachine &TM) {
   PM.add(createTargetTransformInfoWrapperPass(TM.getTargetIRAnalysis()));
 
   // Add optimizations
   PMB.populateThinLTOPassManager(PM);
 
   PM.run(TheModule);
 }
 
+// Parse inline ASM and collect the list of symbols that are not defined in
+// the current module. This is inspired from IRObjectFile.
+static void CollectAsmUndefinedRefs(Module &TheModule,
+                                    StringSet<> &AsmUndefinedRefs) {
+  const std::string &InlineAsm = TheModule.getModuleInlineAsm();
+  if (InlineAsm.empty())
+    return;
+
+  Triple TT(TheModule.getTargetTriple());
+  std::string Err;
+  const Target *T = TargetRegistry::lookupTarget(TT.str(), Err);
+  if (!T)
+    return;
+
+  std::unique_ptr<MCRegisterInfo> MRI(T->createMCRegInfo(TT.str()));
+  if (!MRI)
+    return;
+
+  std::unique_ptr<MCAsmInfo> MAI(T->createMCAsmInfo(*MRI, TT.str()));
+  if (!MAI)
+    return;
+
+  std::unique_ptr<MCSubtargetInfo> STI(
+      T->createMCSubtargetInfo(TT.str(), "", ""));
+  if (!STI)
+    return;
+
+  std::unique_ptr<MCInstrInfo> MCII(T->createMCInstrInfo());
+  if (!MCII)
+    return;
+
+  MCObjectFileInfo MOFI;
+  MCContext MCCtx(MAI.get(), MRI.get(), &MOFI);
+  MOFI.InitMCObjectFileInfo(TT, Reloc::Default, CodeModel::Default, MCCtx);
+  std::unique_ptr<RecordStreamer> Streamer(new RecordStreamer(MCCtx));
+  T->createNullTargetStreamer(*Streamer);
+
+  std::unique_ptr<MemoryBuffer> Buffer(MemoryBuffer::getMemBuffer(InlineAsm));
+  SourceMgr SrcMgr;
+  SrcMgr.AddNewSourceBuffer(std::move(Buffer), SMLoc());
+  std::unique_ptr<MCAsmParser> Parser(
+      createMCAsmParser(SrcMgr, MCCtx, *Streamer, *MAI));
+
+  MCTargetOptions MCOptions;
+  std::unique_ptr<MCTargetAsmParser> TAP(
+      T->createMCAsmParser(*STI, *Parser, *MCII, MCOptions));
+  if (!TAP)
+    return;
+
+  Parser->setTargetParser(*TAP);
+  if (Parser->Run(false))
+    return;
+
+  for (auto &KV : *Streamer) {
+    StringRef Key = KV.first();
+    RecordStreamer::State Value = KV.second;
+    switch (Value) {
+    case RecordStreamer::NeverSeen:
+      llvm_unreachable("InlineASM error");
+    case RecordStreamer::DefinedGlobal:
+    case RecordStreamer::Defined:
+      break;
+    case RecordStreamer::Global:
+    case RecordStreamer::Used:
+      if (!TheModule.getNamedValue(Key))
+        AsmUndefinedRefs.insert(Key);
+      break;
+    }
+  }
+}
+
+//
+static DenseSet<const GlobalValue *> computePreservedSymbolsForModule(
+    Module &TheModule, const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
+    const FunctionImporter::ExportSetTy &ExportList) {
+  DenseSet<const GlobalValue *> PreservedGV;
+  if (GUIDPreservedSymbols.empty())
+    // Be friendly and don't nuke totally the module when the client didn't
+    // supply anything to preserve.
+    return PreservedGV;
+
+  // Declare a callback for the internalize pass that will ask for every
+  // candidate GlobalValue if it can be internalized or not.
+  auto AddPreserveGV = [&](const GlobalValue &GV) {
+    auto GUID = GV.getGUID();
+    if (GUIDPreservedSymbols.count(GUID) || ExportList.count(GUID))
+      PreservedGV.insert(&GV);
+  };
+
+  for (auto &GV : TheModule)
+    AddPreserveGV(GV);
+  for (auto &GV : TheModule.globals())
+    AddPreserveGV(GV);
+  for (auto &GV : TheModule.aliases())
+    AddPreserveGV(GV);
+
+  return PreservedGV;
+}
+
+// Run internalization on \p TheModule
+static void
+internalizeModule(Module &TheModule, const TargetMachine &TM,
+                  const DenseSet<const GlobalValue *> &PreservedGV) {
+  if (PreservedGV.empty()) {
+    // Be friendly and don't nuke totally the module when the client didn't
+    // supply anything to preserve.
+    return;
+  }
+  StringSet<> AsmUndefinedRefs;
+  CollectAsmUndefinedRefs(TheModule, AsmUndefinedRefs);
+
+  // Update the llvm.compiler_used globals to force preserving libcalls and
+  // symbols referenced from asm
+  UpdateCompilerUsed(TheModule, TM, AsmUndefinedRefs);
+
+  // Declare a callback for the internalize pass that will ask for every
+  // candidate GlobalValue if it can be internalized or not.
+  auto MustPreserveGV =
+      [&](const GlobalValue &GV) -> bool { return PreservedGV.count(&GV); };
+
+  llvm::internalizeModule(TheModule, MustPreserveGV);
+}
+
+// Convert the PreservedSymbols map from "Name" based to "GUID" based.
+static DenseSet<GlobalValue::GUID>
+computeGUIDPreservedSymbols(const StringSet<> &PreservedSymbols,
+                            const Triple &TheTriple) {
+  DenseSet<GlobalValue::GUID> GUIDPreservedSymbols(PreservedSymbols.size());
+  for (auto &Entry : PreservedSymbols) {
+    StringRef Name = Entry.first();
+    if (TheTriple.isOSBinFormatMachO() && Name.size() > 0 && Name[0] == '_')
+      Name = Name.drop_front();
+    GUIDPreservedSymbols.insert(GlobalValue::getGUID(Name));
+  }
+  return GUIDPreservedSymbols;
+}
+
 std::unique_ptr<MemoryBuffer> codegenModule(Module &TheModule,
                                             TargetMachine &TM) {
   SmallVector<char, 128> OutputBuffer;
 
   // CodeGen
   {
     raw_svector_ostream OS(OutputBuffer);
     legacy::PassManager PM;
for (auto &Entry : PreservedSymbols) {
       if (DefinedFunctions.count(Entry))
         Hasher.update(
             ArrayRef<uint8_t>((uint8_t *)&Entry, sizeof(GlobalValue::GUID)));
     }
 
     sys::path::append(EntryPath, CachePath, toHex(Hasher.result()));
   }
 
+  // Access the path to this entry in the cache.
+  StringRef getEntryPath() { return EntryPath; }
+
   // Try loading the buffer for this cache entry.
   ErrorOr<std::unique_ptr<MemoryBuffer>> tryLoadingBuffer() {
     if (EntryPath.empty())
       return std::error_code();
     return MemoryBuffer::getFile(EntryPath);
   }
 
   // Cache the Produced object file
void write(MemoryBufferRef OutputBuffer) {
     sys::fs::rename(TempFilename, EntryPath);
   }
 };
 
 static std::unique_ptr<MemoryBuffer> ProcessThinLTOModule(
     Module &TheModule, const ModuleSummaryIndex &Index,
     StringMap<MemoryBufferRef> &ModuleMap, TargetMachine &TM,
     const FunctionImporter::ImportMapTy &ImportList,
+    const FunctionImporter::ExportSetTy &ExportList,
+    const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols,
     std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
     ThinLTOCodeGenerator::CachingOptions CacheOptions, bool DisableCodeGen,
     StringRef SaveTempsDir, unsigned count) {
 
   // Save temps: after IPO.
   saveTempBitcode(TheModule, SaveTempsDir, count, ".1.IPO.bc");
 
+  // Prepare for internalization by computing the set of symbols to preserve.
+  // We need to compute the list of symbols to preserve during internalization
+  // before doing any promotion because after renaming we won't (easily) match
+  // to the original name.
+  auto PreservedGV = computePreservedSymbolsForModule(
+      TheModule, GUIDPreservedSymbols, ExportList);
+
   // "Benchmark"-like optimization: single-source case
   bool SingleModule = (ModuleMap.size() == 1);
 
   if (!SingleModule) {
     promoteModule(TheModule, Index);
 
     // Resolve the LinkOnce/Weak ODR, trying to turn them into
     // "available_externally" when possible.
     // This is a compile-time optimization.
     fixupODR(TheModule, ResolvedODR);
 
     // Save temps: after promotion.
     saveTempBitcode(TheModule, SaveTempsDir, count, ".2.promoted.bc");
+  }
 
+  // Internalization
+  internalizeModule(TheModule, TM, PreservedGV);
+
+  // Save internalized bitcode
+  saveTempBitcode(TheModule, SaveTempsDir, count, ".3.internalized.bc");
+
+  if (!SingleModule) {
     crossImportIntoModule(TheModule, Index, ModuleMap, ImportList);
 
     // Save temps: after cross-module import.
-    saveTempBitcode(TheModule, SaveTempsDir, count, ".3.imported.bc");
+    saveTempBitcode(TheModule, SaveTempsDir, count, ".4.imported.bc");
   }
 
   optimizeModule(TheModule, TM);
 
-  saveTempBitcode(TheModule, SaveTempsDir, count, ".3.opt.bc");
+  saveTempBitcode(TheModule, SaveTempsDir, count, ".5.opt.bc");
 
   if (DisableCodeGen) {
     // Configured to stop before CodeGen, serialize the bitcode and return.
     SmallVector<char, 128> OutputBuffer;
     {
       raw_svector_ostream OS(OutputBuffer);
       ModuleSummaryIndexBuilder IndexBuilder(&TheModule);
       WriteBitcodeToFile(&TheModule, OS, true, &IndexBuilder.getIndex());
#endif
   Modules.push_back(Buffer);
 }
 
 void ThinLTOCodeGenerator::preserveSymbol(StringRef Name) {
   PreservedSymbols.insert(Name);
 }
 
 void ThinLTOCodeGenerator::crossReferenceSymbol(StringRef Name) {
-  CrossReferencedSymbols.insert(Name);
+  // At the moment, we don't take advantage of this extra information, we're
+  // conservatively considering cross-references as preserved.
+  //  CrossReferencedSymbols.insert(Name);
+  PreservedSymbols.insert(Name);
 }
 
 // TargetMachine factory
 std::unique_ptr<TargetMachine> TargetMachineBuilder::create() const {
   std::string ErrMsg;
   const Target *TheTarget =
       TargetRegistry::lookupTarget(TheTriple.str(), ErrMsg);
   if (!TheTarget) {
void ThinLTOCodeGenerator::run() {
   // combined index.
   StringMap<FunctionImporter::ImportMapTy> ImportLists(ModuleCount);
   StringMap<FunctionImporter::ExportSetTy> ExportLists(ModuleCount);
   ComputeCrossModuleImport(*Index, ModuleToDefinedGVSummaries, ImportLists,
                            ExportLists);
 
   // Convert the preserved symbols set from string to GUID, this is needed for
   // computing the caching.
-  DenseSet<GlobalValue::GUID> GUIDPreservedSymbols(PreservedSymbols.size());
-  for (auto &Entry : PreservedSymbols)
-    GUIDPreservedSymbols.insert(GlobalValue::getGUID(Entry.first()));
+  auto GUIDPreservedSymbols =
+      computeGUIDPreservedSymbols(PreservedSymbols, TMBuilder.TheTriple);
 
   // Parallel optimizer + codegen
   {
     ThreadPool Pool(ThreadCount);
     int count = 0;
     for (auto &ModuleBuffer : Modules) {
       Pool.async([&](int count) {
         auto ModuleIdentifier = ModuleBuffer.getBufferIdentifier();
         auto &ExportList = ExportLists[ModuleIdentifier];
 
         auto &DefinedFunctions = ModuleToDefinedGVSummaries[ModuleIdentifier];
+        auto &ExportList = ExportLists[ModuleIdentifier];
 
         // Resolve ODR, this has to be done early because it impacts the caching
         std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> ResolvedODR;
-        ResolveODR(*Index, ExportList, DefinedFunctions,
-                   ModuleIdentifier, ResolvedODR);
+        ResolveODR(*Index, ExportList, DefinedFunctions, ModuleIdentifier,
+                   ResolvedODR);
 
         // The module may be cached, this helps handling it.
-        ModuleCacheEntry CacheEntry(
-            CacheOptions.Path, *Index, ModuleBuffer.getBufferIdentifier(),
-            ImportLists[ModuleBuffer.getBufferIdentifier()],
-            ExportLists[ModuleBuffer.getBufferIdentifier()], ResolvedODR,
-            DefinedFunctions, GUIDPreservedSymbols);
+        ModuleCacheEntry CacheEntry(CacheOptions.Path, *Index, ModuleIdentifier,
+                                    ImportLists[ModuleIdentifier], ExportList,
+                                    ResolvedODR, DefinedFunctions,
+                                    GUIDPreservedSymbols);
 
         {
           auto ErrOrBuffer = CacheEntry.tryLoadingBuffer();
+          DEBUG(dbgs() << "Cache " << (ErrOrBuffer ? "hit" : "miss") << " '"
+                       << CacheEntry.getEntryPath() << "' for buffer " << count
+                       << " " << ModuleIdentifier << "\n");
+
           if (ErrOrBuffer) {
             // Cache Hit!
             ProducedBinaries[count] = std::move(ErrOrBuffer.get());
             return;
           }
         }
 
         LLVMContext Context;
         Context.setDiscardValueNames(LTODiscardValueNames);
 
         // Parse module now
         auto TheModule = loadModuleFromBuffer(ModuleBuffer, Context, false);
 
         // Save temps: original file.
-        if (!SaveTempsDir.empty()) {
-          saveTempBitcode(*TheModule, SaveTempsDir, count, ".0.original.bc");
-        }
 
         auto &ImportList = ImportLists[ModuleIdentifier];
+        // Run the main process now, and generates a binary
         auto OutputBuffer = ProcessThinLTOModule(
             *TheModule, *Index, ModuleMap, *TMBuilder.create(), ImportList,
-            ResolvedODR, CacheOptions, DisableCodeGen, SaveTempsDir, count);
+            ExportList, GUIDPreservedSymbols, ResolvedODR, CacheOptions,
+            DisableCodeGen, SaveTempsDir, count);
 
         CacheEntry.write(*OutputBuffer);
         ProducedBinaries[count] = std::move(OutputBuffer);
       }, count);
       count++;
     }
   }
 

lib/Object/IRObjectFile.cpp

 //===- IRObjectFile.cpp - IR object file implementation ---------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Part of the IRObjectFile class implementation.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Object/IRObjectFile.h"
-#include "RecordStreamer.h"
+#include "llvm/Object/RecordStreamer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Bitcode/ReaderWriter.h"
 #include "llvm/IR/GVMaterializer.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Mangler.h"
 #include "llvm/IR/Module.h"
 #include "llvm/MC/MCAsmInfo.h"
 #include "llvm/MC/MCContext.h"

lib/Object/RecordStreamer.cpp

 //===-- RecordStreamer.cpp - Record asm definde and used symbols ----------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
-#include "RecordStreamer.h"
+#include "llvm/Object/RecordStreamer.h"
 #include "llvm/MC/MCSymbol.h"
 using namespace llvm;
 
 void RecordStreamer::markDefined(const MCSymbol &Symbol) {
   State &S = Symbols[Symbol.getName()];
   switch (S) {
   case DefinedGlobal:
   case Global: