[Merge SImilar Function ThinLTO 3/n] Add hash code to function summary

[hiraditya]

Summary

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

[brzycki]

Hi @hiraditya , pardon my ignorance in this part of llvm. Most of my comments are questions about your reasoning.

lib/Transforms/IPO/MergeSimilarFunctions.cpp

73–74

Why did you change these to externs?

89

Where is this function defined now?

92

Was this intentional, to add this diff with the entire profile function commented out?

1139

Maybe comment here that 0 is a placeholder/invalid hash?

1169

(same comment)

[evgeny777]

Yeah, I'm also wondering what's this for.

lib/Bitcode/Reader/BitcodeReader.cpp

5275

Are we no longer suggested to parse older index files?

[tejohnson]

lib/Transforms/IPO/MergeSimilarFunctions.cpp

1231

Where/how is this used by the patch? I don't see any use here. I tried finding in one of the other 4 related patches, but didn't see it being used there either.

[hiraditya]

lib/Transforms/IPO/MergeSimilarFunctions.cpp

92

Yes, the function definitions are now in ModuleSummaryAnalysis.cpp and the cl::opt is also referred there so I had to make them extern.

1139

Good point!

1231

I'll remove this one.

[hiraditya]

Remove ModuleSummaryIndex

[hiraditya]

Comment

[hiraditya]

rebase

[hiraditya]

port to llvm bitcode version 8

[vish99]

Changes to the merge the 5 patches together

include/llvm/IR/ModuleSummaryIndex.h

 #include <cstdint>
 #include <map>
 #include <memory>
 #include <set>
 #include <string>
 #include <utility>
 #include <vector>
 
+namespace Opt {
+enum MergeLevelEnum { none, size, all };
+}
+
 namespace llvm {
 
+// This is for now until I figure out a better place to put this declaration in.
+// Compute a similarity metric for function F. Useful for merging functions.
+unsigned profileFunction(const Function *F);
+bool isComparisonCandidate(const Function *F);
+bool isAliasCapable(const Function* G);
+
 namespace yaml {
 
 template <typename T> struct MappingTraits;
 
 } // end namespace yaml
 
 /// Class to accumulate and hold information about a callee.
 struct CalleeInfo {

         FunctionSummary::GVFlags(
             GlobalValue::LinkageTypes::AvailableExternallyLinkage,
             /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false),
         0, FunctionSummary::FFlags{}, std::vector<ValueInfo>(),
         std::move(Edges), std::vector<GlobalValue::GUID>(),
         std::vector<FunctionSummary::VFuncId>(),
         std::vector<FunctionSummary::VFuncId>(),
         std::vector<FunctionSummary::ConstVCall>(),
-        std::vector<FunctionSummary::ConstVCall>());
+        std::vector<FunctionSummary::ConstVCall>(), 0);
   }
 
   /// A dummy node to reference external functions that aren't in the index
   static FunctionSummary ExternalNode;
 
 private:
   /// Number of instructions (ignoring debug instructions, e.g.) computed
   /// during the initial compile step when the summary index is first built.
   unsigned InstCount;
 
   /// Function attribute flags. Used to track if a function accesses memory,
   /// 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;
 
 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,
-                  std::vector<ConstVCall> TypeCheckedLoadConstVCalls)
+                  std::vector<ConstVCall> TypeCheckedLoadConstVCalls,
+                  unsigned SimHash)
       : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
         InstCount(NumInsts), FunFlags(FunFlags),
-        CallGraphEdgeList(std::move(CGEdges)) {
+        CallGraphEdgeList(std::move(CGEdges)),
+        SimilarityHash(SimHash) {
     if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
         !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
         !TypeCheckedLoadConstVCalls.empty())
       TIdInfo = llvm::make_unique<TypeIdInfo>(TypeIdInfo{
           std::move(TypeTests), std::move(TypeTestAssumeVCalls),
           std::move(TypeCheckedLoadVCalls),
           std::move(TypeTestAssumeConstVCalls),
           std::move(TypeCheckedLoadConstVCalls)});
   }
 
   /// 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 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/IR/ModuleSummaryIndexYAML.h

           GlobalValueSummary::GVFlags(
               static_cast<GlobalValue::LinkageTypes>(FSum.Linkage),
               FSum.NotEligibleToImport, FSum.Live, FSum.IsLocal),
           0, FunctionSummary::FFlags{}, Refs,
           ArrayRef<FunctionSummary::EdgeTy>{}, std::move(FSum.TypeTests),
           std::move(FSum.TypeTestAssumeVCalls),
           std::move(FSum.TypeCheckedLoadVCalls),
           std::move(FSum.TypeTestAssumeConstVCalls),
-          std::move(FSum.TypeCheckedLoadConstVCalls)));
+          std::move(FSum.TypeCheckedLoadConstVCalls), 0));
     }
   }
   static void output(IO &io, GlobalValueSummaryMapTy &V) {
     for (auto &P : V) {
       std::vector<FunctionSummaryYaml> FSums;
       for (auto &Sum : P.second.SummaryList) {
         if (auto *FSum = dyn_cast<FunctionSummary>(Sum.get())) {
           std::vector<uint64_t> Refs;

include/llvm/Transforms/IPO.h

 /// createHotColdSplittingPass - This pass outlines cold blocks into a separate
 /// function(s).
 ModulePass *createHotColdSplittingPass();
 
 //===----------------------------------------------------------------------===//
 /// createMergeSimilarFunctionsPass - This pass discovers similar functions and
 /// merges them.
 ///
-ModulePass *createMergeSimilarFunctionsPass();
+ModulePass *createMergeSimilarFunctionsPass(const ModuleSummaryIndex *S = nullptr);
 
 //===----------------------------------------------------------------------===//
 /// createPartialInliningPass - This pass inlines parts of functions.
 ///
 ModulePass *createPartialInliningPass();
 
 //===----------------------------------------------------------------------===//
 /// createBarrierNoopPass - This pass is purely a module pass barrier in a pass

lib/Analysis/ModuleSummaryAnalysis.cpp

 cl::opt<FunctionSummary::ForceSummaryHotnessType, true> FSEC(
     "force-summary-edges-cold", cl::Hidden, cl::location(ForceSummaryEdgesCold),
     cl::desc("Force all edges in the function summary to cold"),
     cl::values(clEnumValN(FunctionSummary::FSHT_None, "none", "None."),
                clEnumValN(FunctionSummary::FSHT_AllNonCritical,
                           "all-non-critical", "All non-critical edges."),
                clEnumValN(FunctionSummary::FSHT_All, "all", "All edges.")));
 
+cl::opt<bool> UseGlobalAliases(
+    "mergesimilarfunc-global-aliases", cl::Hidden, cl::init(false),
+    cl::desc("Enable writing alias by enabling global aliases"));
+
+cl::opt<unsigned> MergeMinInsts(
+    "mergesimilarfunc-min-insts", cl::Hidden, cl::init(4),
+    cl::desc("Min instructions required to even consider single block fns"));
+
+// Minimize the name pollution caused by the enum values.
+namespace Opt {
+cl::opt<enum MergeLevelEnum> MergeLevel(
+    "mergesimilarfunc-level", cl::Hidden, cl::ZeroOrMore,
+    cl::desc("Level of function merging:"), cl::init(size),
+    cl::values(clEnumVal(none, "function merging disabled"),
+               clEnumVal(size, "only try to merge functions that are optimized "
+                               "for size"),
+               clEnumVal(all, "attempt to merge all similar functions")));
+}
+
+namespace llvm {
+
+static const char *MERGED_SUFFIX = "__merged";
+
+/// Returns the type id for a type to be hashed. We turn pointer types into
+/// integers here because the actual compare logic below considers pointers and
+/// integers of the same size as equal.
+static Type::TypeID getTypeIDForHash(Type *Ty) {
+  if (Ty->isPointerTy())
+    return Type::IntegerTyID;
+  return Ty->getTypeID();
+}
+
+bool isAliasCapable(const Function* G) {
+  return
+    UseGlobalAliases && G->hasGlobalUnnamedAddr()
+    && (G->hasExternalLinkage() || G->hasLocalLinkage() || G->hasWeakLinkage());
+}
+
+bool isComparisonCandidate(const Function *F) {
+  if (Opt::MergeLevel == Opt::size) {
+    // Only consider functions that are to be optimized for size.
+    // By default, that is all functions at -Os/-Oz and nothing at -O2.
+    bool Os = F->getAttributes().
+      hasAttribute(AttributeList::FunctionIndex, Attribute::OptimizeForSize);
+    bool Oz = F->getAttributes().
+      hasAttribute(AttributeList::FunctionIndex, Attribute::MinSize);
+    if (!Os && !Oz)
+      return false;
+  }
+
+  // Ignore declarations and tiny functions - no point in merging those
+  if (F->isDeclaration()) return false;
+  if (F->getName().endswith(MERGED_SUFFIX)) return false;
+  if (F->hasAvailableExternallyLinkage()) return false;
+  if (F->hasFnAttribute(Attribute::AlwaysInline)) return false;
+  if (F->size() == 1 && F->begin()->size() < MergeMinInsts)
+    return isAliasCapable(F);
+
+  return true;
+}
+
+unsigned profileFunction(const Function *F) {
+  FunctionType *FTy = F->getFunctionType();
+  if (!isComparisonCandidate(F))
+    return 0;
+
+  FoldingSetNodeID ID;
+  ID.AddInteger(F->size());
+  ID.AddInteger(F->getCallingConv());
+  ID.AddBoolean(F->hasGC());
+  ID.AddBoolean(F->isInterposable());
+  ID.AddBoolean(FTy->isVarArg());
+  ID.AddInteger(getTypeIDForHash(FTy->getReturnType()));
+  for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
+    ID.AddInteger(getTypeIDForHash(FTy->getParamType(i)));
+  return ID.ComputeHash();
+}
+}
+
 // Walk through the operands of a given User via worklist iteration and populate
 // the set of GlobalValue references encountered. Invoked either on an
 // Instruction or a GlobalVariable (which walks its initializer).
 static void findRefEdges(ModuleSummaryIndex &Index, const User *CurUser,
                          SetVector<ValueInfo> &RefEdges,
                          SmallPtrSet<const User *, 8> &Visited) {
   SmallVector<const User *, 32> Worklist;
   Worklist.push_back(CurUser);

   bool NonRenamableLocal = isNonRenamableLocal(F);
   bool NotEligibleForImport =
       NonRenamableLocal || HasInlineAsmMaybeReferencingInternal ||
       // Inliner doesn't handle variadic functions.
       // FIXME: refactor this to use the same code that inliner is using.
       F.isVarArg() ||
       // Don't try to import functions with noinline attribute.
       F.getAttributes().hasFnAttribute(Attribute::NoInline);
+  // SimHash of 0 means just a placeholder.
+  unsigned SimHash = llvm::profileFunction(&F);
+
   GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
                                     /* Live = */ false, F.isDSOLocal());
   FunctionSummary::FFlags FunFlags{
       F.hasFnAttribute(Attribute::ReadNone),
       F.hasFnAttribute(Attribute::ReadOnly),
       F.hasFnAttribute(Attribute::NoRecurse),
       F.returnDoesNotAlias(),
   };
   auto FuncSummary = llvm::make_unique<FunctionSummary>(
       Flags, NumInsts, FunFlags, RefEdges.takeVector(),
       CallGraphEdges.takeVector(), TypeTests.takeVector(),
       TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
       TypeTestAssumeConstVCalls.takeVector(),
-      TypeCheckedLoadConstVCalls.takeVector());
+      TypeCheckedLoadConstVCalls.takeVector(), SimHash);
   if (NonRenamableLocal)
     CantBePromoted.insert(F.getGUID());
   Index.addGlobalValueSummary(F, std::move(FuncSummary));
 }
 
 static void
 computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V,
                        DenseSet<GlobalValue::GUID> &CantBePromoted) {

                         F->hasFnAttribute(Attribute::ReadOnly),
                         F->hasFnAttribute(Attribute::NoRecurse),
                         F->returnDoesNotAlias()},
                     ArrayRef<ValueInfo>{}, ArrayRef<FunctionSummary::EdgeTy>{},
                     ArrayRef<GlobalValue::GUID>{},
                     ArrayRef<FunctionSummary::VFuncId>{},
                     ArrayRef<FunctionSummary::VFuncId>{},
                     ArrayRef<FunctionSummary::ConstVCall>{},
-                    ArrayRef<FunctionSummary::ConstVCall>{});
+                    ArrayRef<FunctionSummary::ConstVCall>{}, 0);
             Index.addGlobalValueSummary(*GV, std::move(Summary));
           } else {
             std::unique_ptr<GlobalVarSummary> Summary =
                 llvm::make_unique<GlobalVarSummary>(GVFlags,
                                                     ArrayRef<ValueInfo>{});
             Index.addGlobalValueSummary(*GV, std::move(Summary));
           }
         });

lib/AsmParser/LLParser.cpp

     return true;
 
   auto FS = llvm::make_unique<FunctionSummary>(
       GVFlags, InstCount, FFlags, std::move(Refs), std::move(Calls),
       std::move(TypeIdInfo.TypeTests),
       std::move(TypeIdInfo.TypeTestAssumeVCalls),
       std::move(TypeIdInfo.TypeCheckedLoadVCalls),
       std::move(TypeIdInfo.TypeTestAssumeConstVCalls),
-      std::move(TypeIdInfo.TypeCheckedLoadConstVCalls));
+      std::move(TypeIdInfo.TypeCheckedLoadConstVCalls), 0);
 
   FS->setModulePath(ModulePath);
 
   AddGlobalValueToIndex(Name, GUID, (GlobalValue::LinkageTypes)GVFlags.Linkage,
                         ID, std::move(FS));
 
   return false;
 }

lib/Bitcode/Reader/BitcodeReader.cpp

     }
     case bitc::FS_VALUE_GUID: { // [valueid, refguid]
       uint64_t ValueID = Record[0];
       GlobalValue::GUID RefGUID = Record[1];
       ValueIdToValueInfoMap[ValueID] =
           std::make_pair(TheIndex.getOrInsertValueInfo(RefGUID), RefGUID);
       break;
     }
-    // FS_PERMODULE: [valueid, flags, instcount, fflags, numrefs,
+    // FS_PERMODULE: [valueid, flags, instcount, fflags, simhash, numrefs,
     //                numrefs x valueid, n x (valueid)]
-    // FS_PERMODULE_PROFILE: [valueid, flags, instcount, fflags, numrefs,
+    // FS_PERMODULE_PROFILE: [valueid, flags, instcount, fflags, simhash, numrefs,
     //                        numrefs x valueid,
     //                        n x (valueid, hotness)]
     // FS_PERMODULE_RELBF: [valueid, flags, instcount, fflags, numrefs,
     //                      numrefs x valueid,
     //                      n x (valueid, relblockfreq)]
     case bitc::FS_PERMODULE:
     case bitc::FS_PERMODULE_RELBF:
     case bitc::FS_PERMODULE_PROFILE: {
       unsigned ValueID = Record[0];
       uint64_t RawFlags = Record[1];
       unsigned InstCount = Record[2];
       uint64_t RawFunFlags = 0;
+      unsigned SimHash = 0;
       unsigned NumRefs = Record[3];
       int RefListStartIndex = 4;
       if (Version >= 4) {
         RawFunFlags = Record[3];
-        NumRefs = Record[4];
-        RefListStartIndex = 5;
+        SimHash = Record[4];
+        NumRefs = Record[5];
+        RefListStartIndex = 6;
       }
 
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
       // The module path string ref set in the summary must be owned by the
       // index's module string table. Since we don't have a module path
       // string table section in the per-module index, we create a single
       // module path string table entry with an empty (0) ID to take
       // ownership.
       int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs;
       assert(Record.size() >= RefListStartIndex + NumRefs &&
              "Record size inconsistent with number of references");
       std::vector<ValueInfo> Refs = makeRefList(
           ArrayRef<uint64_t>(Record).slice(RefListStartIndex, NumRefs));
       bool HasProfile = (BitCode == bitc::FS_PERMODULE_PROFILE);
       bool HasRelBF = (BitCode == bitc::FS_PERMODULE_RELBF);
       std::vector<FunctionSummary::EdgeTy> Calls = makeCallList(
           ArrayRef<uint64_t>(Record).slice(CallGraphEdgeStartIndex),
           IsOldProfileFormat, HasProfile, HasRelBF);
       auto FS = llvm::make_unique<FunctionSummary>(
           Flags, InstCount, getDecodedFFlags(RawFunFlags), std::move(Refs),
           std::move(Calls), std::move(PendingTypeTests),
           std::move(PendingTypeTestAssumeVCalls),
           std::move(PendingTypeCheckedLoadVCalls),
           std::move(PendingTypeTestAssumeConstVCalls),
-          std::move(PendingTypeCheckedLoadConstVCalls));
+          std::move(PendingTypeCheckedLoadConstVCalls), SimHash);
       PendingTypeTests.clear();
       PendingTypeTestAssumeVCalls.clear();
       PendingTypeCheckedLoadVCalls.clear();
       PendingTypeTestAssumeConstVCalls.clear();
       PendingTypeCheckedLoadConstVCalls.clear();
       auto VIAndOriginalGUID = getValueInfoFromValueId(ValueID);
       FS->setModulePath(getThisModule()->first());
       FS->setOriginalName(VIAndOriginalGUID.second);

           makeRefList(ArrayRef<uint64_t>(Record).slice(2));
       auto FS = llvm::make_unique<GlobalVarSummary>(Flags, std::move(Refs));
       FS->setModulePath(getThisModule()->first());
       auto GUID = getValueInfoFromValueId(ValueID);
       FS->setOriginalName(GUID.second);
       TheIndex.addGlobalValueSummary(GUID.first, std::move(FS));
       break;
     }
-    // FS_COMBINED: [valueid, modid, flags, instcount, fflags, numrefs,
+    // FS_COMBINED: [valueid, modid, flags, instcount, fflags, simhash, numrefs,
     //               numrefs x valueid, n x (valueid)]
-    // FS_COMBINED_PROFILE: [valueid, modid, flags, instcount, fflags, numrefs,
+    // FS_COMBINED_PROFILE: [valueid, modid, flags, instcount, fflags, simhash, numrefs,
     //                       numrefs x valueid, n x (valueid, hotness)]
     case bitc::FS_COMBINED:
     case bitc::FS_COMBINED_PROFILE: {
       unsigned ValueID = Record[0];
       uint64_t ModuleId = Record[1];
       uint64_t RawFlags = Record[2];
       unsigned InstCount = Record[3];
       uint64_t RawFunFlags = 0;
+      unsigned SimHash = 0;
       unsigned NumRefs = Record[4];
       int RefListStartIndex = 5;
 
       if (Version >= 4) {
         RawFunFlags = Record[4];
-        NumRefs = Record[5];
-        RefListStartIndex = 6;
+        SimHash = Record[5];
+        NumRefs = Record[6];
+        RefListStartIndex = 7;
       }
 
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
       int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs;
       assert(Record.size() >= RefListStartIndex + NumRefs &&
              "Record size inconsistent with number of references");
       std::vector<ValueInfo> Refs = makeRefList(
           ArrayRef<uint64_t>(Record).slice(RefListStartIndex, NumRefs));
       bool HasProfile = (BitCode == bitc::FS_COMBINED_PROFILE);
       std::vector<FunctionSummary::EdgeTy> Edges = makeCallList(
           ArrayRef<uint64_t>(Record).slice(CallGraphEdgeStartIndex),
           IsOldProfileFormat, HasProfile, false);
       ValueInfo VI = getValueInfoFromValueId(ValueID).first;
       auto FS = llvm::make_unique<FunctionSummary>(
           Flags, InstCount, getDecodedFFlags(RawFunFlags), std::move(Refs),
           std::move(Edges), std::move(PendingTypeTests),
           std::move(PendingTypeTestAssumeVCalls),
           std::move(PendingTypeCheckedLoadVCalls),
           std::move(PendingTypeTestAssumeConstVCalls),
-          std::move(PendingTypeCheckedLoadConstVCalls));
+          std::move(PendingTypeCheckedLoadConstVCalls), SimHash);
       PendingTypeTests.clear();
       PendingTypeTestAssumeVCalls.clear();
       PendingTypeCheckedLoadVCalls.clear();
       PendingTypeTestAssumeConstVCalls.clear();
       PendingTypeCheckedLoadConstVCalls.clear();
       LastSeenSummary = FS.get();
       LastSeenGUID = VI.getGUID();
       FS->setModulePath(ModuleIdMap[ModuleId]);

lib/Bitcode/Writer/BitcodeWriter.cpp

 
   FunctionSummary *FS = cast<FunctionSummary>(Summary);
   std::set<GlobalValue::GUID> ReferencedTypeIds;
   writeFunctionTypeMetadataRecords(Stream, FS, ReferencedTypeIds);
 
   NameVals.push_back(getEncodedGVSummaryFlags(FS->flags()));
   NameVals.push_back(FS->instCount());
   NameVals.push_back(getEncodedFFlags(FS->fflags()));
+  NameVals.push_back(FS->similarityHash());
   NameVals.push_back(FS->refs().size());
 
   for (auto &RI : FS->refs())
     NameVals.push_back(VE.getValueID(RI.getValue()));
 
   bool HasProfileData =
       F.hasProfileData() || ForceSummaryEdgesCold != FunctionSummary::FSHT_None;
   for (auto &ECI : FS->calls()) {

 
   // Abbrev for FS_PERMODULE_PROFILE.
   auto Abbv = std::make_shared<BitCodeAbbrev>();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_PROFILE));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));   // flags
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // fflags
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // simhash
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
   // numrefs x valueid, n x (valueid, hotness)
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
   unsigned FSCallsProfileAbbrev = Stream.EmitAbbrev(std::move(Abbv));
 
   // Abbrev for FS_PERMODULE or FS_PERMODULE_RELBF.
   Abbv = std::make_shared<BitCodeAbbrev>();
   if (WriteRelBFToSummary)
     Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_RELBF));
   else
     Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));   // flags
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // fflags
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // simhash
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
   // numrefs x valueid, n x (valueid [, rel_block_freq])
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
   unsigned FSCallsAbbrev = Stream.EmitAbbrev(std::move(Abbv));
 
   // Abbrev for FS_PERMODULE_GLOBALVAR_INIT_REFS.
   Abbv = std::make_shared<BitCodeAbbrev>();

   // Abbrev for FS_COMBINED.
   auto Abbv = std::make_shared<BitCodeAbbrev>();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));   // flags
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // fflags
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // simhash
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
   // numrefs x valueid, n x (valueid)
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
   unsigned FSCallsAbbrev = Stream.EmitAbbrev(std::move(Abbv));
 
   // Abbrev for FS_COMBINED_PROFILE.
   Abbv = std::make_shared<BitCodeAbbrev>();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_PROFILE));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));   // flags
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // fflags
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // simhash
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
   // numrefs x valueid, n x (valueid, hotness)
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
   unsigned FSCallsProfileAbbrev = Stream.EmitAbbrev(std::move(Abbv));
 
   // Abbrev for FS_COMBINED_GLOBALVAR_INIT_REFS.
   Abbv = std::make_shared<BitCodeAbbrev>();

     auto *FS = cast<FunctionSummary>(S);
     writeFunctionTypeMetadataRecords(Stream, FS, ReferencedTypeIds);
 
     NameVals.push_back(*ValueId);
     NameVals.push_back(Index.getModuleId(FS->modulePath()));
     NameVals.push_back(getEncodedGVSummaryFlags(FS->flags()));
     NameVals.push_back(FS->instCount());
     NameVals.push_back(getEncodedFFlags(FS->fflags()));
+    NameVals.push_back(FS->similarityHash());
     // Fill in below
     NameVals.push_back(0);
 
     unsigned Count = 0;
     for (auto &RI : FS->refs()) {
       auto RefValueId = getValueId(RI.getGUID());
       if (!RefValueId)
         continue;

lib/Transforms/IPO/MergeSimilarFunctions.cpp

 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/ModuleSummaryIndex.h"
 #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/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");
 STATISTIC(NumThunksWritten, "Number of thunks generated");
 STATISTIC(NumAliasesWritten, "Number of aliases generated");
 STATISTIC(NumDoubleWeak, "Number of new functions created");
 STATISTIC(NumMultiMerged, "Number of multi-merged functions");
 
 STATISTIC(NumSimilarFunctionsMerged, "Number of similar functions merged");
 
-static cl::opt<unsigned> MergeMinInsts(
-    "mergesimilarfunc-min-insts", cl::Hidden, cl::init(4),
-    cl::desc("Min instructions required to even consider single block fns"));
-
 static cl::opt<unsigned> MergeDifferingMinInsts(
     "mergesimilarfunc-diff-min-insts", cl::Hidden, cl::init(15),
     cl::desc("Min instructions required to try merging differing functions"));
 
 static cl::opt<unsigned> MergeMaxDiffering(
     "mergesimilarfunc-max-diff", cl::Hidden, cl::init(8),
     cl::desc("Maximum number of differing instructions allowed"));
 
 static cl::opt<unsigned> MergeMinSimilarity(
     "mergesimilarfunc-min-similarity", cl::Hidden, cl::init(70),
     cl::desc("Minimum percentage of similar instructions required"));
 
 static cl::opt<bool> OptPrintMerges("mergesimilarfunc-print-merges", cl::Hidden,
                                     cl::init(false));
 
-static cl::opt<bool> UseGlobalAliases(
-    "mergesimilarfunc-global-aliases", cl::Hidden, cl::init(false),
-    cl::desc("Enable writing alias by enabling global aliases"));
+extern cl::opt<bool> UseGlobalAliases;
+extern cl::opt<unsigned> MergeMinInsts;
 
 void PrintMerges(const char *Desc, Function *Old, Function *New) {
   if (OptPrintMerges) {
     dbgs() << "=== [" << Desc << "] replacing " << Old->getName() << " with "
            << New->getName() << "\n";
   }
 }
 
-// Minimize the name pollution caused by the enum values.
 namespace Opt {
-enum MergeLevelEnum { none, size, all };
-static cl::opt<enum MergeLevelEnum> MergeLevel(
-    "mergesimilarfunc-level", cl::Hidden, cl::ZeroOrMore,
-    cl::desc("Level of function merging:"), cl::init(size),
-    cl::values(clEnumVal(none, "function merging disabled"),
-               clEnumVal(size, "only try to merge functions that are optimized "
-                               "for size"),
-               clEnumVal(all, "attempt to merge all similar functions")));
+  extern cl::opt<enum MergeLevelEnum> MergeLevel;
 }
 
 static const char *MERGED_SUFFIX = "__merged";
+namespace llvm {
+unsigned profileFunction(const Function *F);
+}
 
+/*
 /// Returns the type id for a type to be hashed. We turn pointer types into
 /// integers here because the actual compare logic below considers pointers and
 /// integers of the same size as equal.
 static Type::TypeID getTypeIDForHash(Type *Ty) {
   if (Ty->isPointerTy())
     return Type::IntegerTyID;
   return Ty->getTypeID();
 }
 
 /// Creates a hash-code for the function which is the same for any two
 /// functions that will compare equal, without looking at the instructions
 /// inside the function.
-static unsigned profileFunction(const Function *F) {
+namespace llvm {
+unsigned profileFunction(const Function *F) {
   FunctionType *FTy = F->getFunctionType();
 
   FoldingSetNodeID ID;
   ID.AddInteger(F->size());
   ID.AddInteger(F->getCallingConv());
   ID.AddBoolean(F->hasGC());
   ID.AddBoolean(F->isInterposable());
   ID.AddBoolean(FTy->isVarArg());
   ID.AddInteger(getTypeIDForHash(FTy->getReturnType()));
   for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
     ID.AddInteger(getTypeIDForHash(FTy->getParamType(i)));
   return ID.ComputeHash();
 }
-
+}*/
 
 /// Replace Inst1 by a switch statement that executes Inst1 or one of Inst2s
 /// depending on the value of SwitchVal. If a value in Inst2s is NULL, it
 /// defaults to executing Inst1. Returns set of terminator instructions of newly
 /// created switch blocks in Ret.
 ///
 /// For instance, the transformation may look as follows:
 ///         ...Head...

        I != E; ++I) {
     FunctionComparator *FC = *I;
     delete FC;
   }
   FunctionsToMerge.clear();
   FunctionsToCompare.clear();
 }
 
-static bool isAliasCapable(Function* G) {
-  return
-    UseGlobalAliases && G->hasGlobalUnnamedAddr()
-    && (G->hasExternalLinkage() || G->hasLocalLinkage() || G->hasWeakLinkage());
-}
-
-static bool isComparisonCandidate(Function *F) {
-  if (Opt::MergeLevel == Opt::size) {
-    // Only consider functions that are to be optimized for size.
-    // By default, that is all functions at -Os/-Oz and nothing at -O2.
-    bool Os = F->getAttributes().
-      hasAttribute(AttributeList::FunctionIndex, Attribute::OptimizeForSize);
-    bool Oz = F->getAttributes().
-      hasAttribute(AttributeList::FunctionIndex, Attribute::MinSize);
-    if (!Os && !Oz)
-      return false;
-  }
-
-  // Ignore declarations and tiny functions - no point in merging those
-  if (F->isDeclaration()) return false;
-  if (F->getName().endswith(MERGED_SUFFIX)) return false;
-  if (F->hasAvailableExternallyLinkage()) return false;
-  if (F->hasFnAttribute(Attribute::AlwaysInline)) return false;
-  if (F->size() == 1 && F->begin()->size() < MergeMinInsts)
-    return isAliasCapable(F);
-
-  return true;
-}
-
 void MergeRegistry::defer(Function *F) {
   if (isComparisonCandidate(F))
     Deferred.push_back(F);
 }
 
 // Move functions from Deferred into buckets. remove() may have been called
 // multiple times for the same function, so eliminate duplicates using the
 // set. We reverse them because MergeSimilarFunctions::insert inserts at the
 // front of each bucket.
 unsigned MergeRegistry::enqueue() {
   DenseSet<Function *> InsertedFuncs;
 
   for (std::vector<WeakVH>::reverse_iterator
       DefI = Deferred.rbegin(), DefE = Deferred.rend();
       DefI != DefE; ++DefI) {
     Value *V = *DefI;
     Function *F = dyn_cast_or_null<Function>(V);
     if (!F) continue;
     if (InsertedFuncs.find(F) != InsertedFuncs.end()) continue;
-    if (!isComparisonCandidate(F)) continue;
 
     unsigned Hash = profileFunction(F);
+    if (Hash == 0)
+      continue;
     FunctionsToCompare[Hash].push_front(F);
 
     InsertedFuncs.insert(F);
   }
 
   Deferred.clear();
 
   return InsertedFuncs.size();
 }
 
 void MergeRegistry::insertCandidate(FunctionComparator *Comp) {
   FunctionsToMerge.push_back(Comp);

       return;
     }
   }
 }
 
 void MergeRegistry::remove(Function *F, bool Reanalyze/*=true*/) {
   // There is no need to remove a function that is not already
   // in a bucket.
-  if (!isComparisonCandidate(F))
+  unsigned Hash = profileFunction(F);
+  if (Hash == 0)
     return;
 
-  unsigned Hash = profileFunction(F);
   std::list<ComparableFunction> &Bucket = FunctionsToCompare[Hash];
 
   removeFromBucket(F, Bucket);
 
   if (Reanalyze)
     Deferred.push_back(F);
 
   // Check whether we have any existing FunctionComparator objects for this fn.
   // If yes, discard them because F has changed. Retry merging for those

 
   return 0;
 }
 
 namespace {
 
 class MergeSimilarFunctions : public ModulePass {
 public:
   static char ID;
-  MergeSimilarFunctions()
-    : ModulePass(ID) {
+  const ModuleSummaryIndex *Summary;
+  MergeSimilarFunctions(const ModuleSummaryIndex *Summary = nullptr)
+    : ModulePass(ID), Summary(Summary) {
     initializeMergeSimilarFunctionsPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnModule(Module &M);
 
 private:
   /// Find the functions that use this Value and remove them from FnSet and
   /// queue the functions.
   void removeUsers(Value *V);
 
   /// Replace all direct calls of Old with calls of New. Will bitcast New if
   /// necessary to make types match.

 };
 
 }  // end anonymous namespace
 
 char MergeSimilarFunctions::ID = 0;
 INITIALIZE_PASS(MergeSimilarFunctions, "mergesimilarfunc",
                 "Merge Similar Functions", false, false)
 
-ModulePass *llvm::createMergeSimilarFunctionsPass() {
-  return new MergeSimilarFunctions();
+ModulePass *llvm::createMergeSimilarFunctionsPass(const ModuleSummaryIndex *S) {
+  return new MergeSimilarFunctions(S);
 }
 
 bool MergeSimilarFunctions::runOnModule(Module &M) {
   if (Opt::MergeLevel == Opt::none)
     return false;
 
   bool Changed = false;
 

lib/Transforms/IPO/PassManagerBuilder.cpp

     if (PerformThinLTO) {
       // Drop available_externally and unreferenced globals. This is necessary
       // with ThinLTO in order to avoid leaving undefined references to dead
       // globals in the object file.
       MPM.add(createEliminateAvailableExternallyPass());
       MPM.add(createGlobalDCEPass());
     }
 
-    if (EnableMergeSimilarFunctions)
-      MPM.add(createMergeSimilarFunctionsPass());
+    if (EnableMergeSimilarFunctions) {
+      auto *Summary = (ImportSummary ? ImportSummary : ExportSummary);
+      MPM.add(createMergeSimilarFunctionsPass(Summary));
+    }
 
     addExtensionsToPM(EP_EnabledOnOptLevel0, MPM);
 
     // Rename anon globals to be able to export them in the summary.
     // This has to be done after we add the extensions to the pass manager
     // as there could be passes (e.g. Adddress sanitizer) which introduce
     // new unnamed globals.
     if (PrepareForLTO || PrepareForThinLTO)

   if (OptLevel > 1) {
     MPM.add(createGlobalDCEPass());         // Remove dead fns and globals.
     MPM.add(createConstantMergePass());     // Merge dup global constants
   }
 
   if (MergeFunctions)
     MPM.add(createMergeFunctionsPass());
 
-  if (EnableMergeSimilarFunctions)
-    MPM.add(createMergeSimilarFunctionsPass());
+  if (EnableMergeSimilarFunctions) {
+    auto *Summary = (ImportSummary ? ImportSummary : ExportSummary);
+    MPM.add(createMergeSimilarFunctionsPass(Summary));
+  }
 
   // LoopSink pass sinks instructions hoisted by LICM, which serves as a
   // canonicalization pass that enables other optimizations. As a result,
   // LoopSink pass needs to be a very late IR pass to avoid undoing LICM
   // result too early.
   MPM.add(createLoopSinkPass());
   // Get rid of LCSSA nodes.
   MPM.add(createInstSimplifyLegacyPass());

 
   // Now that we have optimized the program, discard unreachable functions.
   PM.add(createGlobalDCEPass());
 
   // FIXME: this is profitable (for compiler time) to do at -O0 too, but
   // currently it damages debug info.
   if (MergeFunctions)
     PM.add(createMergeFunctionsPass());
-  if (EnableMergeSimilarFunctions)
-    PM.add(createMergeSimilarFunctionsPass());
+  if (EnableMergeSimilarFunctions) {
+    auto *Summary = (ImportSummary ? ImportSummary : ExportSummary);
+    PM.add(createMergeSimilarFunctionsPass(Summary));
+  }
 }
 
 void PassManagerBuilder::populateThinLTOPassManager(
     legacy::PassManagerBase &PM) {
   PerformThinLTO = true;
   if (LibraryInfo)
     PM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
 

test/Transforms/MergeSimilarFunc/merge-debug-info.ll

 !5 = !DIDerivedType(tag: DW_TAG_typedef, name: "str_type", file: !1, line: 8, baseType: !6)
 !6 = !DICompositeType(tag: DW_TAG_structure_type, name: "str_type", file: !1, line: 3, size: 96, align: 32, elements: !7)
 !7 = !{!8, !10, !12}
 !8 = !DIDerivedType(tag: DW_TAG_member, name: "x", scope: !6, file: !1, line: 5, baseType: !9, size: 32, align: 32)
 !9 = !DIDerivedType(tag: DW_TAG_pointer_type, baseType: null, size: 32, align: 32)
 !10 = !DIDerivedType(tag: DW_TAG_member, name: "set", scope: !6, file: !1, line: 6, baseType: !11, size: 32, align: 32, offset: 32)
 !11 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
 !12 = !DIDerivedType(tag: DW_TAG_member, name: "get", scope: !6, file: !1, line: 7, baseType: !11, size: 32, align: 32, offset: 64)
-!14 = distinct !DISubprogram(name: "bar", scope: !1, file: !1, line: 10, type: !15, isLocal: false, isDefinition: true, scopeLine: 10, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !17)
+!14 = distinct !DISubprogram(name: "bar", scope: !1, file: !1, line: 10, type: !15, isLocal: false, isDefinition: true, scopeLine: 10, flags: DIFlagPrototyped, isOptimized: true, unit: !0)
 !15 = !DISubroutineType(types: !16)
 !16 = !{!11, !9}
 !17 = !{!18, !19, !20}
 !18 = !DILocalVariable(name: "b", arg: 1, scope: !14, file: !1, line: 10, type: !9)
 !19 = !DILocalVariable(name: "res", scope: !14, file: !1, line: 11, type: !11)
 !20 = !DILocalVariable(name: "ee", scope: !14, file: !1, line: 12, type: !4)
-!21 = distinct !DISubprogram(name: "bar1", scope: !1, file: !1, line: 24, type: !15, isLocal: false, isDefinition: true, scopeLine: 24, flags: DIFlagPrototyped, isOptimized: true, unit: !0, variables: !22)
+!21 = distinct !DISubprogram(name: "bar1", scope: !1, file: !1, line: 24, type: !15, isLocal: false, isDefinition: true, scopeLine: 24, flags: DIFlagPrototyped, isOptimized: true, unit: !0)
 !22 = !{!23, !24, !25}
 !23 = !DILocalVariable(name: "b", arg: 1, scope: !21, file: !1, line: 24, type: !9)
 !24 = !DILocalVariable(name: "res", scope: !21, file: !1, line: 25, type: !11)
 !25 = !DILocalVariable(name: "ee", scope: !21, file: !1, line: 26, type: !4)
 !26 = !{i32 2, !"Dwarf Version", i32 4}
 !27 = !{i32 2, !"Debug Info Version", i32 3}
 !28 = !{!"Clang $LLVM_VERSION_MAJOR.$LLVM_VERSION_MINOR (based on LLVM 3.9.0)"}
 !31 = !{!32, !32, i64 0}