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

(On Diff #169613)

Why did you change these to externs?

89 ↗

(On Diff #169613)

Where is this function defined now?

92 ↗

(On Diff #169613)

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

1137 ↗

(On Diff #169613)

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

1169 ↗

(On Diff #169613)

(same comment)

[evgeny777]

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

lib/Bitcode/Reader/BitcodeReader.cpp

5275 ↗

(On Diff #169613)

Are we no longer suggested to parse older index files?

[tejohnson]

lib/Transforms/IPO/MergeSimilarFunctions.cpp

1228 ↗

(On Diff #169613)

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 ↗

(On Diff #169613)

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

1137 ↗

(On Diff #169613)

Good point!

1228 ↗

(On Diff #169613)

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

llvm/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 {
return FunctionSummary(
             /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false,
             /*CanAutoHide=*/false),
         /*InsCount=*/0, FunctionSummary::FFlags{}, /*EntryCount=*/0,
         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 summary specific flags.
   FFlags FunFlags;
 
   /// The synthesized entry count of the function.
   /// This is only populated during ThinLink phase and remains unused while
   /// generating per-module summaries.
   uint64_t EntryCount = 0;
 
   /// 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,
                   uint64_t EntryCount, 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), EntryCount(EntryCount),
-        CallGraphEdgeList(std::move(CGEdges)) {
+        CallGraphEdgeList(std::move(CGEdges)),
+        SimilarityHash(SimHash) {
     if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
         !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
         !TypeCheckedLoadConstVCalls.empty())
       TIdInfo = std::make_unique<TypeIdInfo>(TypeIdInfo{
           std::move(TypeTests), std::move(TypeTestAssumeVCalls),
           std::move(TypeCheckedLoadVCalls),
           std::move(TypeTestAssumeConstVCalls),
           std::move(TypeCheckedLoadConstVCalls)});
   }
   // Gets the number of readonly and writeonly refs in RefEdgeList
   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; }
+  
   /// 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; }

llvm/include/llvm/IR/ModuleSummaryIndexYAML.h

for (auto &FSum : FSums) {
       for (auto &RefGUID : FSum.Refs) {
         if (!V.count(RefGUID))
           V.emplace(RefGUID, /*IsAnalysis=*/false);
         Refs.push_back(ValueInfo(/*IsAnalysis=*/false, &*V.find(RefGUID)));
       }
       Elem.SummaryList.push_back(std::make_unique<FunctionSummary>(
           GlobalValueSummary::GVFlags(
               static_cast<GlobalValue::LinkageTypes>(FSum.Linkage),
               FSum.NotEligibleToImport, FSum.Live, FSum.IsLocal, FSum.CanAutoHide),
           /*NumInsts=*/0, FunctionSummary::FFlags{}, /*EntryCount=*/0, 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;

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

 void runWholeProgramDevirtOnIndex(
     ModuleSummaryIndex &Summary, std::set<GlobalValue::GUID> &ExportedGUIDs,
     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,
-    function_ref<bool(StringRef, ValueInfo)> isExported,
+    StringMap<FunctionImporter::ExportSetTy> &ExportLists,
     std::map<ValueInfo, std::vector<VTableSlotSummary>> &LocalWPDTargetsMap);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_IPO_WHOLEPROGRAMDEVIRT_H

llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

GlobalValueSummary::GVFlags Flags(F.getLinkage(), NotEligibleForImport,
                                     F.hasLinkOnceODRLinkage() && F.hasGlobalUnnamedAddr());
   FunctionSummary::FFlags FunFlags{
       F.hasFnAttribute(Attribute::ReadNone),
       F.hasFnAttribute(Attribute::ReadOnly),
       F.hasFnAttribute(Attribute::NoRecurse), F.returnDoesNotAlias(),
       // FIXME: refactor this to use the same code that inliner is using.
       // 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);
   auto FuncSummary = std::make_unique<FunctionSummary>(
       Flags, NumInsts, FunFlags, /*EntryCount=*/0, std::move(Refs),
       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));
 }
 
 /// Find function pointers referenced within the given vtable initializer
 /// (or subset of an initializer) \p I. The starting offset of \p I within
 /// the vtable initializer is \p StartingOffset. Any discovered function
ModuleSymbolTable::CollectAsmSymbols(
                         /* NoInline = */ false,
                         F->hasFnAttribute(Attribute::AlwaysInline)},
                     /*EntryCount=*/0, 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 =
                 std::make_unique<GlobalVarSummary>(
                     GVFlags,
                     GlobalVarSummary::GVarFlags(
                         false, false, cast<GlobalVariable>(GV)->isConstant(),
                         GlobalObject::VCallVisibilityPublic),

llvm/lib/AsmParser/LLParser.cpp

if (ParseToken(lltok::rparen, "expected ')' here"))
     return true;
 
   auto FS = std::make_unique<FunctionSummary>(
       GVFlags, InstCount, FFlags, /*EntryCount=*/0, 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;
 }

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

// Parse version
     Expected<unsigned> MaybeRecord = Stream.readRecord(Entry.ID, Record);
     if (!MaybeRecord)
       return MaybeRecord.takeError();
     if (MaybeRecord.get() != bitc::FS_VERSION)
       return error("Invalid Summary Block: version expected");
   }
   const uint64_t Version = Record[0];
   const bool IsOldProfileFormat = Version == 1;
-  if (Version < 1 || Version > 7)
+  if (Version < 1 || Version > 8)
     return error("Invalid summary version " + Twine(Version) +
-                 ". Version should be in the range [1-7].");
+                 ". Version should be in the range [1-8].");
   Record.clear();
 
   // Keep around the last seen summary to be used when we see an optional
   // "OriginalName" attachement.
   GlobalValueSummary *LastSeenSummary = nullptr;
   GlobalValue::GUID LastSeenGUID = 0;
 
   // We can expect to see any number of type ID information records before
while (true) {
     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,
-    //                numrefs x valueid, n x (valueid)]
+    //                numrefs x valueid, simhash, n x (valueid)]
     // FS_PERMODULE_PROFILE: [valueid, flags, instcount, fflags, numrefs,
-    //                        numrefs x valueid,
+    //                        numrefs x valueid, simhash,
     //                        n x (valueid, hotness)]
     // FS_PERMODULE_RELBF: [valueid, flags, instcount, fflags, numrefs,
-    //                      numrefs x valueid,
+    //                      numrefs x valueid, simhash,
     //                      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];
       unsigned NumRORefs = 0, NumWORefs = 0;
       int RefListStartIndex = 4;
       if (Version >= 4) {
         RawFunFlags = Record[3];
         NumRefs = Record[4];
         RefListStartIndex = 5;
         if (Version >= 5) {
           NumRORefs = Record[5];
           RefListStartIndex = 6;
           if (Version >= 7) {
             NumWORefs = Record[6];
             RefListStartIndex = 7;
+            if (Version >= 8) {
+              SimHash = Record[7];
+              RefListStartIndex = 8;
+            }
           }
         }
       }
 
       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
case bitc::FS_PERMODULE_PROFILE: {
           IsOldProfileFormat, HasProfile, HasRelBF);
       setSpecialRefs(Refs, NumRORefs, NumWORefs);
       auto FS = std::make_unique<FunctionSummary>(
           Flags, InstCount, getDecodedFFlags(RawFunFlags), /*EntryCount=*/0,
           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);
case bitc::FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS: {
       VS->setModulePath(getThisModule()->first());
       VS->setVTableFuncs(VTableFuncs);
       auto GUID = getValueInfoFromValueId(ValueID);
       VS->setOriginalName(GUID.second);
       TheIndex.addGlobalValueSummary(GUID.first, std::move(VS));
       break;
     }
     // FS_COMBINED: [valueid, modid, flags, instcount, fflags, numrefs,
-    //               numrefs x valueid, n x (valueid)]
+    //               numrefs x valueid, simhash, n x (valueid)]
     // FS_COMBINED_PROFILE: [valueid, modid, flags, instcount, fflags, numrefs,
-    //                       numrefs x valueid, n x (valueid, hotness)]
+    //                       numrefs x valueid, simhash, 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;
       uint64_t EntryCount = 0;
       unsigned NumRefs = Record[4];
       unsigned NumRORefs = 0, NumWORefs = 0;
       int RefListStartIndex = 5;
 
       if (Version >= 4) {
         RawFunFlags = Record[4];
         RefListStartIndex = 6;
         size_t NumRefsIndex = 5;
         if (Version >= 5) {
           unsigned NumRORefsOffset = 1;
           RefListStartIndex = 7;
           if (Version >= 6) {
             NumRefsIndex = 6;
             EntryCount = Record[5];
             RefListStartIndex = 8;
             if (Version >= 7) {
               RefListStartIndex = 9;
               NumWORefs = Record[8];
               NumRORefsOffset = 2;
+              if (Version >= 8) {
+                SimHash = Record[9];
+                RefListStartIndex = 10;
+              }
             }
           }
           NumRORefs = Record[RefListStartIndex - NumRORefsOffset];
         }
         NumRefs = Record[NumRefsIndex];
       }
 
       auto Flags = getDecodedGVSummaryFlags(RawFlags, Version);
case bitc::FS_COMBINED_PROFILE: {
       ValueInfo VI = getValueInfoFromValueId(ValueID).first;
       setSpecialRefs(Refs, NumRORefs, NumWORefs);
       auto FS = std::make_unique<FunctionSummary>(
           Flags, InstCount, getDecodedFFlags(RawFunFlags), EntryCount,
           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]);

llvm/lib/Bitcode/Writer/BitcodeWriter.cpp

void ModuleBitcodeWriterBase::writePerModuleFunctionSummaryRecord(
 
   auto SpecialRefCnts = FS->specialRefCounts();
   NameVals.push_back(getEncodedGVSummaryFlags(FS->flags()));
   NameVals.push_back(FS->instCount());
   NameVals.push_back(getEncodedFFlags(FS->fflags()));
   NameVals.push_back(FS->refs().size());
   NameVals.push_back(SpecialRefCnts.first);  // rorefcnt
   NameVals.push_back(SpecialRefCnts.second); // worefcnt
+  NameVals.push_back(FS->similarityHash());  // simhash
 
   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()) {
     NameVals.push_back(getValueId(ECI.first));
Stream.EmitRecord(bitc::FS_PERMODULE_VTABLE_GLOBALVAR_INIT_REFS, NameVals,
                       FSModVTableRefsAbbrev);
   }
   NameVals.clear();
 }
 
 // Current version for the summary.
 // This is bumped whenever we introduce changes in the way some record are
 // interpreted, like flags for instance.
-static const uint64_t INDEX_VERSION = 7;
+static const uint64_t INDEX_VERSION = 8;
 
 /// Emit the per-module summary section alongside the rest of
 /// the module's bitcode.
 void ModuleBitcodeWriterBase::writePerModuleGlobalValueSummary() {
   // By default we compile with ThinLTO if the module has a summary, but the
   // client can request full LTO with a module flag.
   bool IsThinLTO = true;
   if (auto *MD =
void ModuleBitcodeWriterBase::writePerModuleGlobalValueSummary() {
   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, 4));   // numrefs
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // rorefcnt
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // worefcnt
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // simhash
   // 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, 4));   // numrefs
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // rorefcnt
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // worefcnt
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // simhash
   // 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>();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS));
void IndexBitcodeWriter::writeCombinedGlobalValueSummary() {
   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));   // entrycount
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // rorefcnt
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // worefcnt
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // simhash
   // 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));   // entrycount
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // rorefcnt
   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // worefcnt
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // simhash
   // 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>();
   Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_GLOBALVAR_INIT_REFS));
forEachSummary([&](GVInfo I, bool IsAliasee) {
     NameVals.push_back(FS->instCount());
     NameVals.push_back(getEncodedFFlags(FS->fflags()));
     NameVals.push_back(FS->entryCount());
 
     // Fill in below
     NameVals.push_back(0); // numrefs
     NameVals.push_back(0); // rorefcnt
     NameVals.push_back(0); // worefcnt
+    NameVals.push_back(FS->similarityHash()); // simhash
 
     unsigned Count = 0, RORefCnt = 0, WORefCnt = 0;
     for (auto &RI : FS->refs()) {
       auto RefValueId = getValueId(RI.getGUID());
       if (!RefValueId)
         continue;
       NameVals.push_back(*RefValueId);
       if (RI.isReadOnly())

llvm/lib/LTO/ThinLTOCodeGenerator.cpp

 extern cl::opt<std::string> RemarksFilename;
 extern cl::opt<std::string> RemarksPasses;
 extern cl::opt<bool> RemarksWithHotness;
 extern cl::opt<std::string> RemarksFormat;
 }
 
 namespace {
 
-// Default to using all available threads in the system, but using only one
-// thred per core, as indicated by the usage of
-// heavyweight_hardware_concurrency() below.
-static cl::opt<int> ThreadCount("threads", cl::init(0));
+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) {
   if (TempDir.empty())
     return;
   // User asked to save temps, let dump the bitcode file after import.
   std::string SaveTempPath = (TempDir + llvm::Twine(count) + Suffix).str();

llvm/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...
for (std::list<FunctionComparator *>::iterator
        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);
+    // Hash code of 0 is just a placeholder.
+    if (Hash == 0)
+      continue;
     FunctionsToCompare[Hash].push_front(F);
 
     InsertedFuncs.insert(F);
   }
 
   Deferred.clear();
 
   return InsertedFuncs.size();
if (I->getFunc() == F) {
       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);
+  // Hash code of 0 is just a placeholder.
+  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.

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>
-    EnableMatrix("enable-matrix", cl::init(false), cl::Hidden,
-                 cl::desc("Enable lowering of the matrix intrinsics"));
-
 static 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;
if (OptLevel == 0) {
     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) {
+      auto *Summary = (ImportSummary ? ImportSummary : ExportSummary);
+      MPM.add(createMergeSimilarFunctionsPass(Summary));
+    }
+
     addExtensionsToPM(EP_EnabledOnOptLevel0, MPM);
 
     if (PrepareForLTO || PrepareForThinLTO) {
       MPM.add(createCanonicalizeAliasesPass());
       // 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.
void PassManagerBuilder::populateModulePassManager(
   // See comment in the new PM for justification of scheduling splitting at
   // this stage (\ref buildModuleSimplificationPipeline).
   if (EnableHotColdSplit && !(PrepareForLTO || PrepareForThinLTO))
     MPM.add(createHotColdSplittingPass());
 
   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());
void PassManagerBuilder::addLateLTOOptimizationPasses(
 
   // 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));
 

llvm/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}