[Merge SImilar Function ThinLTO 5/n] Set up similar function to be imported

[hiraditya]

Summary

Import the similar functions into the module with another function matching the hash.
Depends on: https://reviews.llvm.org/D53253

[hiraditya]

llvm_debug

[brzycki]

Hi @hiraditya , comments inline.

lib/Transforms/IPO/FunctionImport.cpp

488

ooh boy this is a dense section of code. Possibly consider refactoring into helper functions for readability?

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

488

This is a good suggestion. Also, some high level comments describing what this code is doing/how it works would be helpful.

500

Seems like this should be an actual assert. Actually, there is such an assert below, why the early return - leftover from debugging?

508

You should fix this, and it should be straightforward. See where we check the return value of the ImportList insertion for importing above (variable PreviouslyImported).

512

This could be avoided (and save an expensive hash lookup), if the SimFunctions saved the VIs to start with (although I haven't yet looked through your other patches to see how this is being populated).

519

Why this constraint? Note that any global variables being referenced by an imported function will automatically have their declarations imported too.

[hiraditya]

lib/Transforms/IPO/FunctionImport.cpp

488

Will do that. Thanks for pointing out.

500

yes, this is a leftover.

519

I'll remove this comment. Does not seem to be relevant.

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

519

It isn't just the comment, but also the corresponding check just below that the refs() be empty.

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

519

Note though that in its place you need to ensure that the function is eligible to import (notEligibleToImport() on the function summary), and you should also skip anything that was found to be globally unreachable (isGlobalValueLive() on the index). Not sure about checking whether it has interposable linkage. See some of the checks being done in selectCallee() in this file. Some of those are profitability (related to whether we can inline the imported function), but others are correctness checks. I.e. if it is notEligibleToImport then it might be referencing functions/variables that cannot be promoted to global scope for some reason.

[hiraditya]

rebase

include/llvm/IR/ModuleSummaryIndex.h

   }
 
   /// 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; }
+  unsigned similarityHash() const { 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;
+    ValueInfo VI = getValueInfo(GUID);
+    assert(VI.getSummaryList().size() == 1);
+    GlobalValueSummary *S = VI.getSummaryList()[0].get();
+    assert(isa<FunctionSummary>(S) && "Not a function summary!");
 
     if (FunctionSimilarityHashes.count(GUID)) {
       // Erase the GUID having multiple visits in the ModuleSummaryIndex.
       FunctionSimilarityHashes.erase(GUID);
       DuplicateFunctions.insert(GUID);
       return;
     }
 

lib/Transforms/IPO/FunctionImport.cpp

         return true;
       });
   if (It == CalleeSummaryList.end())
     return nullptr;
 
   return cast<GlobalValueSummary>(It->get());
 }
 
-namespace {
+void addAllCallsAndRefs(const FunctionSummary *FS,
+                        FunctionImporter::ExportSetTy &ExportList) {
+  // 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 : FS->calls()) {
+    auto CalleeGUID = Edge.first.getGUID();
+    ExportList.insert(CalleeGUID);
+  }
+  for (auto &Ref : FS->refs()) {
+    auto GUID = Ref.getGUID();
+    ExportList.insert(GUID);
+  }
+}
 
+namespace {
 using EdgeInfo = std::tuple<const FunctionSummary *, unsigned /* Threshold */,
                             GlobalValue::GUID>;
 
 } // anonymous namespace
 
 static ValueInfo
 updateValueInfoForIndirectCalls(const ModuleSummaryIndex &Index, ValueInfo VI) {
   if (!VI.getSummaryList().empty())

       // We previously decided to import this GUID definition if it was already
       // inserted in the set of imports from the exporting module.
       bool PreviouslyImported = !ILI.second;
 
       // 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);
-          }
-        }
+      if (!PreviouslyImported)
+        addAllCallsAndRefs(ResolvedCalleeSummary, ExportList);
       }
     }
 
     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;
       return Threshold * ImportInstrFactor;
     };
 
     bool IsHotCallsite =
         Edge.second.getHotness() == CalleeInfo::HotnessType::Hot;
     const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite);
 
     ImportCount++;
 
     // Insert the newly imported function to the worklist.
     Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, VI.getGUID());
   }
+
+  // TODO: Do not import too many functions
+  // TODO: Make hashing little more strict to have higher hit rate
+  auto &HostSimilarFunctions = Index.getHostSimilarFunction();
+  if (HostSimilarFunctions.empty())
+    return;
+  // If the function is similar to others and is a host, then import the others
+  auto GUID = Summary.getOriginalName();
+  auto I = HostSimilarFunctions.find(GUID);
+  if (I != HostSimilarFunctions.end()) {
+    // This Function is in the hosting module.
+    unsigned SimHash = Summary.similarityHash();
+    auto &SimFunctionsHash = Index.getSimilarFunctionsHash();
+    unsigned SimHashFromIndex = SimFunctionsHash.find(GUID)->second;
+    assert(SimHash == SimHashFromIndex);
+    auto &SimFunctions = Index.getSimilarFunctions();
+    auto GUIDs = SimFunctions.find(SimHash)->second;
+    for (auto GUID : GUIDs) {
+      // Import GUIDs from outside module.
+      // FIXME: Import a function once ever!
+      // assert if a GUID is exported twice
+      if (!DefinedGVSummaries.count(GUID)) {
+        // Get the Summary from GUID to add to export summary.
+        if (ValueInfo VI = Index.getValueInfo(GUID)) {
+          if (VI.getSummaryList().size() == 1) {
+            GlobalValueSummary *S = VI.getSummaryList()[0].get();
+            auto ExportModulePath = S->modulePath();
+            auto &ProcessPair = ImportList[ExportModulePath][GUID];
+            DEBUG(dbgs() << "\nImporting: " << GUID << ", with Hash: "
+                         << SimHash << ", from: " << ExportModulePath;);
+            // TODO: Do not process same GUID twice!
+            auto &ExportList = (*ExportLists)[ExportModulePath];
+            // Import other dependencies as decl only.
+            auto FS = cast<FunctionSummary>(S);
+            addAllCallsAndRefs(FS, ExportList);
+            ExportList.insert(GUID);
+            // FIXME: Importing only small functions for now.
+            ProcessPair.first = ImportInstrLimit * 2;
+            ProcessPair.second = false; // Import definition.
+          }
+        }
+      } else {
+        auto *S = Index.getValueInfo(GUID).getSummaryList()[0].get();
+        DEBUG(dbgs() << "\nNot importing, Already present: " << GUID
+                     << ", with Hash: " << SimHash
+                     << ", in: " << S->modulePath(););
+      }
+    }
+  }
+
 }
 
 /// Given the list of globals defined in a module, compute the list of imports
 /// as well as the list of "exports", i.e. the list of symbols referenced from
 /// another module (that may require promotion).
 static void ComputeImportForModule(
     const GVSummaryMapTy &DefinedGVSummaries, const ModuleSummaryIndex &Index,
     StringRef ModName, FunctionImporter::ImportMapTy &ImportList,

lib/Transforms/IPO/MergeSimilarFunctions.cpp

 
   bool Changed = false;
 
   DL = &M.getDataLayout();
 
   for (auto &I : M)
     Registry.defer(&I);
 
+  // Populate information from each function summary to module summary index.
+  // create a function like computedevirtualization, like compute merge function
+  // that is like making decision before thinlto starts.
+  // use the index during the thinlto time to do function merging.
+  // TODO: Set the linkage type correctly such that imported function
+  // remains and the other one gets removed by the linker.
   do {
     unsigned InsertCount = Registry.enqueue();
 
     LLVM_DEBUG(dbgs() << "size of module: " << M.size() << '\n');
     LLVM_DEBUG(dbgs() << "size of worklist: " << InsertCount << '\n');
     (void)InsertCount;
 
     Changed |= doExhaustiveCompareMerge();