[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 ↗

(On Diff #169611)

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 ↗

(On Diff #169611)

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

llvm/include/llvm/IR/ModuleSummaryIndex.h

public:
 
   /// 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; }
-  
   /// Get function summary flags.
   FFlags fflags() const { return FunFlags; }
 
   /// Get the instruction count recorded for this function.
   unsigned instCount() const { return InstCount; }
 
   /// Get the synthetic entry count for this function.
   uint64_t entryCount() const { return EntryCount; }
private:
   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;
   }

llvm/include/llvm/Transforms/IPO.h

 // IR metadata to reflect the profile.
 ModulePass *createSampleProfileLoaderPass();
 ModulePass *createSampleProfileLoaderPass(StringRef Name);
 
 /// Write ThinLTO-ready bitcode to Str.
 ModulePass *createWriteThinLTOBitcodePass(raw_ostream &Str,
                                           raw_ostream *ThinLinkOS = nullptr);
 
+/// 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 llvm namespace
 
 #endif

llvm/include/llvm/Transforms/IPO/WholeProgramDevirt.h

void runWholeProgramDevirtOnIndex(
     std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
 
 /// Call after cross-module importing to update the recorded single impl
 /// devirt target names for any locals that were exported.
 void updateIndexWPDForExports(
     ModuleSummaryIndex &Summary,
     StringMap<FunctionImporter::ExportSetTy> &ExportLists,
     std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
-
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H

llvm/lib/LTO/ThinLTOCodeGenerator.cpp

 // Flags -discard-value-names, defined in LTOCodeGenerator.cpp
 extern cl::opt<bool> LTODiscardValueNames;
 extern cl::opt<std::string> RemarksFilename;
 extern cl::opt<std::string> RemarksPasses;
 extern cl::opt<bool> RemarksWithHotness;
 extern cl::opt<std::string> RemarksFormat;
 }
 
+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) {
for (auto &Mod : Modules) {
       }, count++);
     }
 
     return;
   }
 
   // Sequential linking phase
   auto Index = linkCombinedIndex();
+  if (EnableMergeSimilarFunctions)
+    computeMergeSimilarFunctions(*Index);
 
   // Save temps: index.
   if (!SaveTempsDir.empty()) {
     auto SaveTempPath = SaveTempsDir + "index.bc";
     std::error_code EC;
     raw_fd_ostream OS(SaveTempPath, EC, sys::fs::OF_None);
     if (EC)
       report_fatal_error(Twine("Failed to open ") + SaveTempPath +

llvm/lib/Transforms/IPO/FunctionImport.cpp

if (CalleeSummary) {
       if (!PreviouslyImported) {
         NumImportedFunctionsThinLink++;
         if (IsHotCallsite)
           NumImportedHotFunctionsThinLink++;
         if (IsCriticalCallsite)
           NumImportedCriticalFunctionsThinLink++;
       }
 
-      // Any calls/references made by this function will be marked exported
-      // later, in ComputeCrossModuleImport, after import decisions are
-      // complete, which is more efficient than adding them here.
-      if (ExportLists)
-        (*ExportLists)[ExportModulePath].insert(VI);
+      // Make exports in the source module.
+      if (ExportLists) {
+        auto &ExportList = (*ExportLists)[ExportModulePath];
+        ExportList.insert(VI.getGUID());
+        if (!PreviouslyImported) {
+          // This is the first time this function was exported from its source
+          // module, so mark all functions and globals it references as exported
+          // to the outside if they are defined in the same source module.
+          // For efficiency, we unconditionally add all the referenced GUIDs
+          // to the ExportList for this module, and will prune out any not
+          // defined in the module later in a single pass.
+          for (auto &Edge : ResolvedCalleeSummary->calls()) {
+            auto CalleeGUID = Edge.first.getGUID();
+            ExportList.insert(CalleeGUID);
+          }
+          for (auto &Ref : ResolvedCalleeSummary->refs()) {
+            auto GUID = Ref.getGUID();
+            ExportList.insert(GUID);
+          }
+        }
+      }
     }
 
     auto GetAdjustedThreshold = [](unsigned Threshold, bool IsHotCallsite) {
       // Adjust the threshold for next level of imported functions.
       // The threshold is different for hot callsites because we can then
       // inline chains of hot calls.
       if (IsHotCallsite)
         return Threshold * ImportHotInstrFactor;

llvm/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");

 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();
 

llvm/lib/Transforms/IPO/PassManagerBuilder.cpp

cl::opt<bool> FlattenedProfileUsed(
     "flattened-profile-used", cl::init(false), cl::Hidden,
     cl::desc("Indicate the sample profile being used is flattened, i.e., "
              "no inline hierachy exists in the profile. "));
 
 cl::opt<bool> EnableOrderFileInstrumentation(
     "enable-order-file-instrumentation", cl::init(false), cl::Hidden,
     cl::desc("Enable order file instrumentation (default = off)"));
 
-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;