ThinLTO: add module caching handling.

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

343

Unfortunately this is not enough to handle internalization, or linkonce_odr optimization like in D18346, I'll have to give more thought about it.

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

343

Another issue is that promotion will rename later a global with a name that will different between two different links if the object is not in the same position. The hashing here does not account for this unfortunately.
It seems like an intrinsically hard problem to solve (unless we give-up on sharing objects across two different links)

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

343

Unfortunately this is not enough to handle internalization, or linkonce_odr optimization like in D18346, I'll have to give more thought about it.

For the linkonce optimization, how about compute and hash the set of isFirstDefinitionForLinker entries for this module? That is solely based off of summaries.

[mehdi_amini]

Update: fix ODR resolution and preserved symbols (for future internalization).

[mehdi_amini]

Add compiler revision as part of the hash

[mehdi_amini]

Fix build

[tejohnson]

Is this essentially done and ready for re-review? (Realize it is dependent on outstanding patch D18987.)

lib/LTO/ThinLTOCodeGenerator.cpp

408

Not directly related to this patch, but I just noticed that the CacheOptions parameter here is unused.

[mehdi_amini]

No, Not at all, thanks for checking!

[mehdi_amini]

Rebase and update, this one should be good now.

[mehdi_amini]

Fix build

[mehdi_amini]

Rebase

[tejohnson]

Couple small comments, but otherwise, I think this looks good.

include/llvm/ADT/StringExtras.h

62

Use doxygen style comment "///"

lib/LTO/ThinLTOCodeGenerator.cpp

175

Why this change? D18908 uses a DenseMap.

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

175

To compute the hash for the cache, we iterate over the map, so we need a stable ordering.

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

175

Ah, ok. Probably worth a comment.

[mehdi_amini]

Address comments (add a comment for the std::map)

[mehdi_amini]

r266959

include/llvm/ADT/StringExtras.h

while (X) {
     unsigned char Mod = static_cast<unsigned char>(X) & 15;
     *--BufPtr = hexdigit(Mod, LowerCase);
     X >>= 4;
   }
 
   return std::string(BufPtr, std::end(Buffer));
 }
 
+// Convert buffer \p Input to its hexadecimal representation.
+// The returned string is double the size of \p Input.
+static inline std::string toHex(StringRef Input) {
+  static const char *const LUT = "0123456789ABCDEF";
+  size_t Length = Input.size();
+
+  std::string Output;
+  Output.reserve(2 * Length);
+  for (size_t i = 0; i < Length; ++i) {
+    const unsigned char c = Input[i];
+    Output.push_back(LUT[c >> 4]);
+    Output.push_back(LUT[c & 15]);
+  }
+  return Output;
+}
+
 static inline std::string utostr(uint64_t X, bool isNeg = false) {
   char Buffer[21];
   char *BufPtr = std::end(Buffer);
 
   if (X == 0) *--BufPtr = '0';  // Handle special case...
 
   while (X) {
     *--BufPtr = '0' + char(X % 10);

lib/LTO/ThinLTOCodeGenerator.cpp

 
 #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/Config/config.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/SubtargetFeature.h"
 #include "llvm/Object/ModuleSummaryIndexObjectFile.h"
+#include "llvm/Support/CachePruning.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Path.h"
+#include "llvm/Support/SHA1.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/PassManagerBuilder.h"
 #include "llvm/Transforms/ObjCARC.h"

 /// We'd like to drop these function if they are no longer referenced in the
 /// current module. However there is a chance that another module is still
 /// referencing them because of the import. We make sure we always emit at least
 /// one copy.
 static void ResolveODR(
     const ModuleSummaryIndex &Index,
     const std::map<GlobalValue::GUID, GlobalValueSummary *> &DefinedGlobals,
     StringRef ModuleIdentifier,
-    DenseMap<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR) {
+    std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR) {
   // We won't optimize the globals that are referenced by an alias for now
   // Ideally we should turn the alias into a global and duplicate the definition
   // when needed.
   DenseSet<GlobalValueSummary *> GlobalInvolvedWithAlias;
   for (auto &GA : DefinedGlobals) {
     if (auto AS = dyn_cast<AliasSummary>(GA.second))
       GlobalInvolvedWithAlias.insert(&AS->getAliasee());
   }
 
   for (auto &GV : DefinedGlobals) {
     if (GlobalInvolvedWithAlias.count(GV.second))
       continue;
     auto NewLinkage = ResolveODR(Index, ModuleIdentifier, GV.first, *GV.second);
     if (NewLinkage != GV.second->linkage()) {
       ResolvedODR[GV.first] = NewLinkage;
     }
   }
 }
 
 /// Fixup linkage, see ResolveODR() above.
 void fixupODR(
     Module &TheModule,
-    const DenseMap<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR) {
+    const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR) {
   // Process functions and global now
   for (auto &GV : TheModule) {
     auto NewLinkage = ResolvedODR.find(GV.getGUID());
     if (NewLinkage == ResolvedODR.end())
       continue;
     DEBUG(dbgs() << "ODR fixing up linkage for `" << GV.getName() << "` from "
                  << GV.getLinkage() << " to " << NewLinkage->second << "\n");
     GV.setLinkage(NewLinkage->second);
if (TM.addPassesToEmitFile(PM, OS, TargetMachine::CGFT_ObjectFile,
       report_fatal_error("Failed to setup codegen");
 
     // Run codegen now. resulting binary is in OutputBuffer.
     PM.run(TheModule);
   }
   return make_unique<ObjectMemoryBuffer>(std::move(OutputBuffer));
 }
 
+/// Manage caching for a single Module.
+class ModuleCacheEntry {
+  SmallString<128> EntryPath;
+
+public:
+  // Create a cache entry. This compute a unique hash for the Module considering
+  // the current list of export/import, and offer an interface to query to
+  // access the content in the cache.
+  ModuleCacheEntry(
+      StringRef CachePath, const ModuleSummaryIndex &Index, StringRef ModuleID,
+      const FunctionImporter::ImportMapTy &ImportList,
+      const FunctionImporter::ExportSetTy &ExportList,
+      const std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
+      const std::map<GlobalValue::GUID, GlobalValueSummary *> &DefinedFunctions,
+      const DenseSet<GlobalValue::GUID> &PreservedSymbols) {
+    if (CachePath.empty())
+      return;
+
+    // Compute the unique hash for this entry.
+    // This is based on the current compiler version, the module itself, the
+    // export list, the hash for every single module in the import list, the
+    // list of ResolvedODR for the module, and the list of preserved symbols.
+
+    SHA1 Hasher;
+
+    // Start with the compiler revision
+    Hasher.update(LLVM_VERSION_STRING);
+    Hasher.update(LLVM_REVISION_STRING);
+
+
+    // Include the hash for the current module
+    auto ModHash = Index.getModuleHash(ModuleID);
+    Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
+    for (auto F : ExportList)
+      // The export list can impact the internalization, be conservative here
+      Hasher.update(ArrayRef<uint8_t>((uint8_t *)&F, sizeof(F)));
+
+    // Include the hash for every module we import functions from
+    for (auto &Entry : ImportList) {
+      auto ModHash = Index.getModuleHash(Entry.first());
+      Hasher.update(ArrayRef<uint8_t>((uint8_t *)&ModHash[0], sizeof(ModHash)));
+    }
+
+    // Include the hash for the resolved ODR.
+    for (auto &Entry : ResolvedODR) {
+      Hasher.update(ArrayRef<uint8_t>((uint8_t *)&Entry.first,
+                                      sizeof(GlobalValue::GUID)));
+      Hasher.update(ArrayRef<uint8_t>((uint8_t *)&Entry.second,
+                                      sizeof(GlobalValue::LinkageTypes)));
+    }
+
+    // Include the hash for the preserved symbols.
+    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()));
+  }
+
+  // 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) {
+    if (EntryPath.empty())
+      return;
+
+    // Write to a temporary to avoid race condition
+    SmallString<128> TempFilename;
+    int TempFD;
+    std::error_code EC =
+        sys::fs::createTemporaryFile("Thin", "tmp.o", TempFD, TempFilename);
+    if (EC) {
+      errs() << "Error: " << EC.message() << "\n";
+      report_fatal_error("ThinLTO: Can't get a temporary file");
+    }
+    {
+      raw_fd_ostream OS(TempFD, /* ShouldClose */ true);
+      OS << OutputBuffer.getBuffer();
+    }
+    // Rename to final destination (hopefully race condition won't matter here)
+    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,
-    DenseMap<GlobalValue::GUID, GlobalValue::LinkageTypes> &ResolvedODR,
+    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");
 
   // "Benchmark"-like optimization: single-source case
   bool SingleModule = (ModuleMap.size() == 1);
 
void ThinLTOCodeGenerator::promote(Module &TheModule,
   // Collect for each module the list of function it defines (GUID -> Summary).
   StringMap<std::map<GlobalValue::GUID, GlobalValueSummary *>>
       ModuleToDefinedGVSummaries;
   Index.collectDefinedFunctionsPerModule(ModuleToDefinedGVSummaries);
 
   // Resolve the LinkOnceODR, trying to turn them into "available_externally"
   // where possible.
   // This is a compile-time optimization.
-  DenseMap<GlobalValue::GUID, GlobalValue::LinkageTypes> ResolvedODR;
+  std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> ResolvedODR;
   ResolveODR(Index, ModuleToDefinedGVSummaries[ModuleIdentifier],
              ModuleIdentifier, ResolvedODR);
   fixupODR(TheModule, ResolvedODR);
 
   promoteModule(TheModule, Index);
 }
 
 /**
void ThinLTOCodeGenerator::run() {
 
   // Collect the import/export lists for all modules from the call-graph in the
   // 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()));
+
   // Parallel optimizer + codegen
   {
     ThreadPool Pool(ThreadCount);
     int count = 0;
     for (auto &ModuleBuffer : Modules) {
       Pool.async([&](int count) {
-        LLVMContext Context;
-        Context.setDiscardValueNames(LTODiscardValueNames);
         auto ModuleIdentifier = ModuleBuffer.getBufferIdentifier();
+        auto &DefinedFunctions = ModuleToDefinedGVSummaries[ModuleIdentifier];
 
-        DenseMap<GlobalValue::GUID, GlobalValue::LinkageTypes> ResolvedODR;
-        ResolveODR(*Index, ModuleToDefinedGVSummaries[ModuleIdentifier],
-                   ModuleIdentifier, ResolvedODR);
+        // Resolve ODR, this has to be done early because it impacts the caching
+        std::map<GlobalValue::GUID, GlobalValue::LinkageTypes> ResolvedODR;
+        ResolveODR(*Index, 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);
+
+        {
+          auto ErrOrBuffer = CacheEntry.tryLoadingBuffer();
+          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];
-        ProducedBinaries[count] = ProcessThinLTOModule(
+        auto OutputBuffer = ProcessThinLTOModule(
             *TheModule, *Index, ModuleMap, *TMBuilder.create(), ImportList,
             ResolvedODR, CacheOptions, DisableCodeGen, SaveTempsDir, count);
+
+        CacheEntry.write(*OutputBuffer);
+        ProducedBinaries[count] = std::move(OutputBuffer);
       }, count);
       count++;
     }
   }
 
+  CachePruning(CacheOptions.Path)
+      .setPruningInterval(CacheOptions.PruningInterval)
+      .setEntryExpiration(CacheOptions.Expiration)
+      .setMaxSize(CacheOptions.MaxPercentageOfAvailableSpace)
+      .prune();
+
   // If statistics were requested, print them out now.
   if (llvm::AreStatisticsEnabled())
     llvm::PrintStatistics();
 }