Index: include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- include/llvm/IR/ModuleSummaryIndex.h +++ include/llvm/IR/ModuleSummaryIndex.h @@ -43,6 +43,10 @@ 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); + namespace yaml { template struct MappingTraits; @@ -498,7 +502,7 @@ std::vector(), std::vector(), std::vector(), - std::vector()); + std::vector(), 0); } /// A dummy node to reference external functions that aren't in the index @@ -517,6 +521,7 @@ std::vector CallGraphEdgeList; std::unique_ptr TIdInfo; + unsigned SimilarityHash; public: FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags, @@ -525,10 +530,12 @@ std::vector TypeTestAssumeVCalls, std::vector TypeCheckedLoadVCalls, std::vector TypeTestAssumeConstVCalls, - std::vector TypeCheckedLoadConstVCalls) + std::vector 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()) @@ -544,6 +551,9 @@ return GVS->getSummaryKind() == FunctionKind; } + /// Get the SimilarityHash of this function. + unsigned similarityHash() { return SimilarityHash; } + /// Get function attribute flags. FFlags fflags() const { return FunFlags; } Index: include/llvm/IR/ModuleSummaryIndexYAML.h =================================================================== --- include/llvm/IR/ModuleSummaryIndexYAML.h +++ include/llvm/IR/ModuleSummaryIndexYAML.h @@ -230,7 +230,7 @@ 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) { Index: include/llvm/Transforms/IPO.h =================================================================== --- include/llvm/Transforms/IPO.h +++ include/llvm/Transforms/IPO.h @@ -210,7 +210,7 @@ /// createMergeSimilarFunctionsPass - This pass discovers similar functions and /// merges them. /// -ModulePass *createMergeSimilarFunctionsPass(); +ModulePass *createMergeSimilarFunctionsPass(const ModuleSummaryIndex *S = nullptr); //===----------------------------------------------------------------------===// /// createPartialInliningPass - This pass inlines parts of functions. Index: lib/Analysis/ModuleSummaryAnalysis.cpp =================================================================== --- lib/Analysis/ModuleSummaryAnalysis.cpp +++ lib/Analysis/ModuleSummaryAnalysis.cpp @@ -71,6 +71,33 @@ "all-non-critical", "All non-critical edges."), clEnumValN(FunctionSummary::FSHT_All, "all", "All edges."))); +namespace llvm { + +/// 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(); +} + +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(); +} +} + // 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). @@ -345,6 +372,9 @@ 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{ @@ -358,7 +388,7 @@ 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)); @@ -471,7 +501,7 @@ ArrayRef{}, ArrayRef{}, ArrayRef{}, - ArrayRef{}); + ArrayRef{}, 0); Index.addGlobalValueSummary(*GV, std::move(Summary)); } else { std::unique_ptr Summary = Index: lib/AsmParser/LLParser.cpp =================================================================== --- lib/AsmParser/LLParser.cpp +++ lib/AsmParser/LLParser.cpp @@ -7593,7 +7593,7 @@ std::move(TypeIdInfo.TypeTestAssumeVCalls), std::move(TypeIdInfo.TypeCheckedLoadVCalls), std::move(TypeIdInfo.TypeTestAssumeConstVCalls), - std::move(TypeIdInfo.TypeCheckedLoadConstVCalls)); + std::move(TypeIdInfo.TypeCheckedLoadConstVCalls), 0); FS->setModulePath(ModulePath); Index: lib/Bitcode/Reader/BitcodeReader.cpp =================================================================== --- lib/Bitcode/Reader/BitcodeReader.cpp +++ lib/Bitcode/Reader/BitcodeReader.cpp @@ -5250,9 +5250,9 @@ 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, @@ -5265,12 +5265,14 @@ 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); @@ -5295,7 +5297,7 @@ std::move(PendingTypeTestAssumeVCalls), std::move(PendingTypeCheckedLoadVCalls), std::move(PendingTypeTestAssumeConstVCalls), - std::move(PendingTypeCheckedLoadConstVCalls)); + std::move(PendingTypeCheckedLoadConstVCalls), SimHash); PendingTypeTests.clear(); PendingTypeTestAssumeVCalls.clear(); PendingTypeCheckedLoadVCalls.clear(); @@ -5351,9 +5353,9 @@ 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: { @@ -5362,13 +5364,15 @@ 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); @@ -5388,7 +5392,7 @@ std::move(PendingTypeTestAssumeVCalls), std::move(PendingTypeCheckedLoadVCalls), std::move(PendingTypeTestAssumeConstVCalls), - std::move(PendingTypeCheckedLoadConstVCalls)); + std::move(PendingTypeCheckedLoadConstVCalls), SimHash); PendingTypeTests.clear(); PendingTypeTestAssumeVCalls.clear(); PendingTypeCheckedLoadVCalls.clear(); Index: lib/Bitcode/Writer/BitcodeWriter.cpp =================================================================== --- lib/Bitcode/Writer/BitcodeWriter.cpp +++ lib/Bitcode/Writer/BitcodeWriter.cpp @@ -3464,6 +3464,7 @@ 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()) @@ -3556,6 +3557,7 @@ 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)); @@ -3572,6 +3574,7 @@ 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)); @@ -3666,6 +3669,7 @@ 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)); @@ -3680,6 +3684,7 @@ 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)); @@ -3776,6 +3781,7 @@ 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); Index: lib/Transforms/IPO/MergeSimilarFunctions.cpp =================================================================== --- lib/Transforms/IPO/MergeSimilarFunctions.cpp +++ lib/Transforms/IPO/MergeSimilarFunctions.cpp @@ -97,7 +97,11 @@ } 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. @@ -110,7 +114,8 @@ /// 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; @@ -124,7 +129,7 @@ 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 @@ -1256,9 +1261,10 @@ class MergeSimilarFunctions : public ModulePass { public: - static char ID; - MergeSimilarFunctions() - : ModulePass(ID) { + static char ID; + const ModuleSummaryIndex *Summary; + MergeSimilarFunctions(const ModuleSummaryIndex *Summary = nullptr) + : ModulePass(ID), Summary(Summary) { initializeMergeSimilarFunctionsPass(*PassRegistry::getPassRegistry()); } @@ -1325,8 +1331,8 @@ 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) { Index: lib/Transforms/IPO/PassManagerBuilder.cpp =================================================================== --- lib/Transforms/IPO/PassManagerBuilder.cpp +++ lib/Transforms/IPO/PassManagerBuilder.cpp @@ -465,8 +465,10 @@ MPM.add(createGlobalDCEPass()); } - if (EnableMergeSimilarFunctions) - MPM.add(createMergeSimilarFunctionsPass()); + if (EnableMergeSimilarFunctions) { + auto *Summary = (ImportSummary ? ImportSummary : ExportSummary); + MPM.add(createMergeSimilarFunctionsPass(Summary)); + } addExtensionsToPM(EP_EnabledOnOptLevel0, MPM); @@ -730,8 +732,10 @@ 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, @@ -922,8 +926,10 @@ // 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(