[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

1363

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

   /// recurses or aliases.
   FFlags FunFlags;
 
   /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
   std::vector<EdgeTy> CallGraphEdgeList;
 
   std::unique_ptr<TypeIdInfo> TIdInfo;
   unsigned SimilarityHash;
+  /// 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;
 
 public:
   FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
                   std::vector<ValueInfo> Refs, std::vector<EdgeTy> CGEdges,
                   std::vector<GlobalValue::GUID> TypeTests,
                   std::vector<VFuncId> TypeTestAssumeVCalls,
                   std::vector<VFuncId> TypeCheckedLoadVCalls,
                   std::vector<ConstVCall> TypeTestAssumeConstVCalls,

   /// Check if this is a function summary.
   static bool classof(const GlobalValueSummary *GVS) {
     return GVS->getSummaryKind() == FunctionKind;
   }
 
   /// Get the SimilarityHash of this function.
   unsigned similarityHash() { return SimilarityHash; }
 
+  bool hasSimilarFunction(unsigned id) { return SimilarFunctions.count(id); }
+
+  void addToSimilarFunctions(unsigned id, GlobalValue::GUID GUID) {
+    if (id == 0)
+      return; // invalid id.
+    if (DuplicateFunctions.count(GUID))
+      return;
+
+    if (FunctionSimilarityHashes.count(GUID)) {
+      // Erase the GUID having multiple visits in the ModuleSummaryIndex.
+      FunctionSimilarityHashes.erase(GUID);
+      DuplicateFunctions.insert(GUID);
+      return;
+    }
+
+    FunctionSimilarityHashes[GUID] = id;
+  }
+
+  void populateReverseSimilarityHashMap() {
+    for (auto &p : FunctionSimilarityHashes)
+      SimilarFunctions[p.second].push_back(p.first);
+  }
+
+  void removeSingleEntriesFromSimHashMaps() {
+    // Iterate over the hash to remove entries with no duplicates.
+    for (auto I = SimilarFunctions.begin(), E = SimilarFunctions.end();
+         I != E;) {
+      auto Next = std::next(I);
+      assert(I->second.size() && "Empty Entry!");
+      if (I->second.size() == 1) {
+        FunctionSimilarityHashes.erase(I->second[0]);
+        SimilarFunctions.erase(I);
+      }
+      I = Next;
+    }
+  }
+
+  std::map<unsigned, std::vector<GlobalValue::GUID>> &getSimilarFunctions() {
+    return SimilarFunctions;
+  }
+
+  const std::map<unsigned, std::vector<GlobalValue::GUID>> &
+  getSimilarFunctions() const {
+    return SimilarFunctions;
+  }
+
+  unsigned getSimilarityHash(GlobalValue::GUID ID) const {
+    return FunctionSimilarityHashes.find(ID)->second;
+  }
+
+  std::map<GlobalValue::GUID, unsigned> &getSimilarFunctionsHash() {
+    return FunctionSimilarityHashes;
+  }
+
+  const std::map<GlobalValue::GUID, unsigned> &getSimilarFunctionsHash() const {
+    return FunctionSimilarityHashes;
+  }
+
+  void addToHostSimilarFunction(GlobalValue::GUID ID) {
+    HostSimilarFunction.insert(ID);
+  }
+
+  std::set<GlobalValue::GUID> &getHostSimilarFunction() {
+    return HostSimilarFunction;
+  }
+
+  const std::set<GlobalValue::GUID> &getHostSimilarFunction() const {
+    return HostSimilarFunction;
+  }
+
   /// Get function attribute flags.
   FFlags fflags() const { return FunFlags; }
 
   /// Get the instruction count recorded for this function.
   unsigned instCount() const { return InstCount; }
 
   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
   ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }

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;
+      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();
+
+  DEBUG(llvm::errs() << "\nSize SimilarFunctionsHash: "
+                     << Index.getSimilarFunctionsHash().size());
+  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]);
+  }
+  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();
 

 
   Changed |= doDiffMerge();
 
   Registry.clear();
   return Changed;
 }
 
 // Replace direct callers of Old with New.
 void MergeSimilarFunctions::replaceDirectCallers(Function *Old, Function *New) {
   Constant *BitcastNew = ConstantExpr::getBitCast(New, Old->getType());
   for (Value::use_iterator UI = Old->use_begin(), UE = Old->use_end();
        UI != UE;) {
     Use *U = &*UI;
     ++UI;
     CallSite CS(U->getUser());
     if (CS && CS.isCallee(U)) {
       Registry.remove(CS.getInstruction()->getParent()->getParent());

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;