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

(On Diff #169610)

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

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

488 ↗

(On Diff #169610)

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

500 ↗

(On Diff #169610)

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

508 ↗

(On Diff #169610)

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 ↗

(On Diff #169610)

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 ↗

(On Diff #169610)

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 ↗

(On Diff #169610)

Will do that. Thanks for pointing out.

500 ↗

(On Diff #169610)

yes, this is a leftover.

519 ↗

(On Diff #169610)

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

[tejohnson]

lib/Transforms/IPO/FunctionImport.cpp

519 ↗

(On Diff #169610)

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 ↗

(On Diff #169610)

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

llvm/include/llvm/IR/ModuleSummaryIndex.h

public:
   std::pair<unsigned, unsigned> specialRefCounts() const;
 
   /// 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; }
 
   /// 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.

llvm/lib/Transforms/IPO/FunctionImport.cpp

auto It = llvm::find_if(
           return false;
         }
         if (GlobalValue::isInterposableLinkage(GVSummary->linkage())) {
           Reason = FunctionImporter::ImportFailureReason::InterposableLinkage;
           // There is no point in importing these, we can't inline them
           return false;
         }
 
+        if (!isa<FunctionSummary>(GVSummary->getBaseObject()))
+          return false;
         auto *Summary = cast<FunctionSummary>(GVSummary->getBaseObject());
 
         // If this is a local function, make sure we import the copy
         // in the caller's module. The only time a local function can
         // share an entry in the index is if there is a local with the same name
         // in another module that had the same source file name (in a different
         // directory), where each was compiled in their own directory so there
         // was not distinguishing path.
auto It = llvm::find_if(
         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())
if (CalleeSummary) {
         if (IsCriticalCallsite)
           NumImportedCriticalFunctionsThinLink++;
       }
 
       // 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;
     };
 
     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;
+    if (SimHash != SimHashFromIndex) {
+      LLVM_DEBUG(dbgs() << "Assertion failed: (SimHash == SimHashFromIndex);");
+      return;
+    }
+    assert(SimHash == SimHashFromIndex);
+    const auto &SimFunctions = Index.getSimilarFunctions();
+    const 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();
+            // TODO: Explore why GlobalVar is in this set.
+            if (!isa<FunctionSummary>(S))
+              continue;
+            auto FS = cast<FunctionSummary>(S);
+            // TODO: Import declarations of global variables as well.
+            if (FS->refs().size())
+              continue;
+            auto ExportModulePath = S->modulePath();
+            ImportList[ExportModulePath].insert(GUID);
+            LLVM_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.
+            // FIXME: Import only declarations of global variables
+            addAllCallsAndRefs(FS, ExportList);
+            ExportList.insert(GUID);
+          }
+        }
+      } else {
+        auto *S = Index.getValueInfo(GUID).getSummaryList()[0].get();
+        LLVM_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,

llvm/lib/Transforms/IPO/MergeSimilarFunctions.cpp

bool MergeSimilarFunctions::runOnModule(Module &M) {
 
   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();