[Merge SImilar Function ThinLTO 4/n] Make merge function decisions before the thin-lto stage

[hiraditya]

Summary

Make decisions about which functions are to be imported, and the module of the function which will be hosting all the other functions.

Depends on: https://reviews.llvm.org/D52966

[hiraditya]

compiler error

[brzycki]

Hi @hiraditya , comments inline.

lib/Transforms/IPO/MergeSimilarFunctions.cpp

1327

Possibly convert this and the previous line to:

assert(!SimFunctions.count(0) && "Zero hash entries are placeholders");

[tejohnson]

It's hard to review the changes the way they are currently split up. E.g. This patch adds some fields to the index, without using them or testing them. Those changes are in a different patch or two. It would be good to isolate all the changes that create and set these new index fields and test them via dumping the index to assembly and looking for expected values. Then have another patch that uses them in the FunctionImporter. Etc.

Also, it looks like the changes are only enabled for:

• the old pass manager
• the old LTO API (lib/LTO/ThinLTOCodeGenerator.cpp).

Please also add to the new pass manager and the new LTO API (see LTO/LTO.cpp) at the same time.

include/llvm/Transforms/IPO/WholeProgramDevirt.h

234

This isn't the right file to declare this function, which is unrelated to WPD.

[hiraditya]

rebase

[vish99]

Changes to merge the 5 patches together

include/llvm/IR/ModuleSummaryIndex.h

   std::set<std::string> CfiFunctionDefs;
   std::set<std::string> CfiFunctionDecls;
 
   // Used in cases where we want to record the name of a global, but
   // don't have the string owned elsewhere (e.g. the Strtab on a module).
   StringSaver Saver;
   BumpPtrAllocator Alloc;
 
+  /// Functions with hash code as a measure of structural similarity.
+  /// Used by MergeSimilarFunctions. The value_type is the hash code
+  /// computed by profileFunction.
+  std::map<GlobalValue::GUID, unsigned> FunctionSimilarityHashes;
+  /// Reverse map of @var SimilarFunctionsHash to be used during thin-lto.
+  /// Each GUID in the vector corresponds to functions with same hash (id).
+  std::map<unsigned, std::vector<GlobalValue::GUID>> SimilarFunctions;
+  /// Functions having multiple entries in ModuleSummaryIndex.
+  std::set<GlobalValue::GUID> DuplicateFunctions;
+  /// All similar functions w.r.t the one in this set will be imported into
+  /// the module of these functions during thin-lto stage.
+  /// FIXME: Maybe use a vector?
+  std::set<GlobalValue::GUID> HostSimilarFunction;
+
   // YAML I/O support.
   friend yaml::MappingTraits<ModuleSummaryIndex>;
 
   GlobalValueSummaryMapTy::value_type *
   getOrInsertValuePtr(GlobalValue::GUID GUID) {
     return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs))
                  .first;
   }

include/llvm/Transforms/IPO/WholeProgramDevirt.h

   WholeProgramDevirtPass(ModuleSummaryIndex *ExportSummary,
                          const ModuleSummaryIndex *ImportSummary)
       : ExportSummary(ExportSummary), ImportSummary(ImportSummary) {
     assert(!(ExportSummary && ImportSummary));
   }
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &);
 };
 
+/// Decide which functions to import for function merging during the thinlto.
+/// Populates information from each function summary to module summary index.
+void computeMergeSimilarFunctions(ModuleSummaryIndex &Index);
+
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H

lib/LTO/ThinLTOCodeGenerator.cpp

 
 namespace llvm {
 // Flags -discard-value-names, defined in LTOCodeGenerator.cpp
 extern cl::opt<bool> LTODiscardValueNames;
 extern cl::opt<std::string> LTORemarksFilename;
 extern cl::opt<bool> LTOPassRemarksWithHotness;
 }
 
+extern cl::opt<bool> EnableMergeSimilarFunctions;
+
 namespace {
 
 static cl::opt<int>
     ThreadCount("threads", cl::init(llvm::heavyweight_hardware_concurrency()));
 
 // Simple helper to save temporary files for debug.
 static void saveTempBitcode(const Module &TheModule, StringRef TempDir,
                             unsigned count, StringRef Suffix) {

     sys::fs::create_directories(SavedObjectsDirectoryPath);
     bool IsDir;
     sys::fs::is_directory(SavedObjectsDirectoryPath, IsDir);
     if (!IsDir)
       report_fatal_error("Unexistent dir: '" + SavedObjectsDirectoryPath + "'");
     ProducedBinaryFiles.resize(Modules.size());
   }
 
+  if (EnableMergeSimilarFunctions)
+    computeMergeSimilarFunctions(*Index);
+
   if (CodeGenOnly) {
     // Perform only parallel codegen and return.
     ThreadPool Pool;
     int count = 0;
     for (auto &ModuleBuffer : Modules) {
       Pool.async([&](int count) {
         LLVMContext Context;
         Context.setDiscardValueNames(LTODiscardValueNames);

lib/Transforms/IPO/MergeSimilarFunctions.cpp

 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/Format.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 #include <vector>
 #include <list>
 using namespace llvm;
 
 STATISTIC(NumFunctionsMerged, "Number of functions merged");

 char MergeSimilarFunctions::ID = 0;
 INITIALIZE_PASS(MergeSimilarFunctions, "mergesimilarfunc",
                 "Merge Similar Functions", false, false)
 
 ModulePass *llvm::createMergeSimilarFunctionsPass(const ModuleSummaryIndex *S) {
   return new MergeSimilarFunctions(S);
 }
 
+void llvm::computeMergeSimilarFunctions(ModuleSummaryIndex &Index) {
+  assert(Index.getSimilarFunctions().empty() && "Inserting SimHash twice");
+  for (auto &P : Index) {
+    for (auto &S : P.second.SummaryList) {
+      FunctionSummary *FS = dyn_cast<FunctionSummary>(S.get());
+      if (!FS)
+        continue;
+      LLVM_DEBUG(llvm::errs() << "\nSimilarity hash: " << FS->similarityHash());
+      Index.addToSimilarFunctions(FS->similarityHash(), FS->getOriginalName());
+    }
+  }
+  Index.populateReverseSimilarityHashMap();
+  llvm::errs() << "\nSize SimilarFunctionsHash: "
+               << Index.getSimilarFunctionsHash().size();
+  llvm::errs() << "\nSize SimilarFunctions: "
+               << Index.getSimilarFunctions().size();
+  Index.removeSingleEntriesFromSimHashMaps();
+
+  LLVM_DEBUG(llvm::errs() << "\nSize SimilarFunctionsHash: "
+                     << Index.getSimilarFunctionsHash().size());
+  LLVM_DEBUG(llvm::errs() << "\nSize SimilarFunctions: "
+                     << Index.getSimilarFunctions().size());
+
+  auto &SimFunctions = Index.getSimilarFunctions();
+  // Shouldn't have entries with hash of 0, because those are placeholders.
+  assert(!SimFunctions.count(0));
+  auto &HostSimFunction = Index.getHostSimilarFunction();
+  for (auto I = SimFunctions.begin(), E = SimFunctions.end(); I != E; ++I) {
+    // Make the first of all similar functions as host.
+    HostSimFunction.insert(I->second[0]);
+  }
+  LLVM_DEBUG(llvm::errs() << "\nSize getHostSimilarFunction: "
+                     << Index.getHostSimilarFunction().size());
+  return;
+}
+
 bool MergeSimilarFunctions::runOnModule(Module &M) {
   if (Opt::MergeLevel == Opt::none)
     return false;
 
   bool Changed = false;
 
   DL = &M.getDataLayout();
 

lib/Transforms/IPO/PassManagerBuilder.cpp

 static cl::opt<bool> EnableGVNSink(
     "enable-gvn-sink", cl::init(false), cl::Hidden,
     cl::desc("Enable the GVN sinking pass (default = off)"));
 
 static cl::opt<bool>
     EnableCHR("enable-chr", cl::init(true), cl::Hidden,
               cl::desc("Enable control height reduction optimization (CHR)"));
 
-static cl::opt<bool> EnableMergeSimilarFunctions(
+cl::opt<bool> EnableMergeSimilarFunctions(
     "enable-merge-sim-functions", cl::init(false), cl::Hidden,
     cl::desc("Enable the Function merging pass (default = on)"));
 
 PassManagerBuilder::PassManagerBuilder() {
     OptLevel = 2;
     SizeLevel = 0;
     LibraryInfo = nullptr;
     Inliner = nullptr;