ThinLTO: add module caching handling.

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

334

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

334

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

334

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

302–369

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

197–198

Why this change? D18908 uses a DenseMap.

[mehdi_amini]

lib/LTO/ThinLTOCodeGenerator.cpp

197–198

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

[tejohnson]

lib/LTO/ThinLTOCodeGenerator.cpp

197–198

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/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/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"
case GlobalValue::WeakODRLinkage: {
     auto *GVInfo = getGVInfo(GV);
     if (!GVInfo)
       break;
     // We need to emit only one of these, the first module will keep
     // it "as is" and the others will drop it
     if (!IsFirstDefinitionForLinker(*GVInfo, Index, ModulePath))
       GV.setLinkage(GlobalValue::AvailableExternallyLinkage);
     break;
   }
   }
 }
 
 /// LinkOnceODR needs to be turned to weak ODR for correctness.
 ///
 static void FixupLinkOnceODR(Module &TheModule,
                              const ModuleSummaryIndex &Index) {
   for (auto &GV : TheModule) {
     FixupLinkOnceODR(GV, Index, TheModule.getModuleIdentifier());
if (TM.addPassesToEmitFile(PM, OS, TargetMachine::CGFT_ObjectFile,
                                /* DisableVerify */ true))
       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) {
+    if (CachePath.empty())
+      return;
+
+    // Compute the unique hash for this entry
+    // This is based on the module itself, the export list, and the hash for
+    // every single module in the import list
+
+    SHA1 Hasher;
+    // Include the hash for the current module
+    auto ModHash = Index.getModuleHash(ModuleID);
+    Hasher.write((const char *)&ModHash[0], sizeof(ModHash));
+    for (auto F : ExportList)
+      // The export list can impact the internalization, be conservative here
+      Hasher.write((const char *)&F, sizeof(F));
+
+    // Include the hash for every module we import functions from
+    for (auto &Entry : ImportList) {
+      auto ModHash = Index.getModuleHash(Entry.first());
+      Hasher.write((const char *)&ModHash[0], sizeof(ModHash));
+    }
+
+    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,
                      ThinLTOCodeGenerator::CachingOptions CacheOptions,
                      StringRef SaveTempsDir, unsigned count) {
 
   // Save temps: after IPO.
   saveTempBitcode(TheModule, SaveTempsDir, count, ".1.IPO.bc");
void ThinLTOCodeGenerator::run() {
   ComputeCrossModuleImport(*Index, ImportLists, ExportLists);
 
   // Parallel optimizer + codegen
   {
     ThreadPool Pool(ThreadCount);
     int count = 0;
     for (auto &ModuleBuffer : Modules) {
       Pool.async([&](int count) {
+        // The module may be cached, this helps handling it.
+        ModuleCacheEntry CacheEntry(
+            CacheOptions.Path, *Index, ModuleBuffer.getBufferIdentifier(),
+            ImportLists[ModuleBuffer.getBufferIdentifier()],
+            ExportLists[ModuleBuffer.getBufferIdentifier()]);
+
+        {
+          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[TheModule->getModuleIdentifier()];
-        ProducedBinaries[count] = ProcessThinLTOModule(
+
+        auto OutputBuffer = ProcessThinLTOModule(
             *TheModule, *Index, ModuleMap, *TMBuilder.create(), ImportList,
             CacheOptions, 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();
 }