From 5f85a9dedae7fd0aba1292c5e6b3882ca3ee1412 Mon Sep 17 00:00:00 2001 From: Peter Collingbourne Date: Thu, 4 May 2017 03:36:16 +0000 Subject: [PATCH] IR: Use pointers instead of GUIDs to represent edges in the module summary. NFCI. When profiling a no-op incremental link of Chromium I found that the functions computeImportForFunction and computeDeadSymbols were consuming roughly 10% of the profile. The goal of this change is to improve the performance of those functions by changing the map lookups that they were previously doing into pointer dereferences. This is achieved by changing the ValueInfo data structure to be a pointer to an element of the global value map owned by ModuleSummaryIndex, and changing reference lists in the GlobalValueSummary to hold ValueInfos instead of GUIDs. This means that a ValueInfo will take a client directly to the summary list for a given GUID. Differential Revision: https://reviews.llvm.org/D32471 llvm-svn: 302108 --- clang/lib/CodeGen/BackendUtil.cpp | 4 +- llvm/include/llvm/IR/ModuleSummaryIndex.h | 152 ++++++++++++------------- llvm/include/llvm/IR/ModuleSummaryIndexYAML.h | 4 +- llvm/lib/Analysis/ModuleSummaryAnalysis.cpp | 43 +++---- llvm/lib/Bitcode/Reader/BitcodeReader.cpp | 77 +++++++------ llvm/lib/Bitcode/Writer/BitcodeWriter.cpp | 22 ++-- llvm/lib/IR/ModuleSummaryIndex.cpp | 12 +- llvm/lib/LTO/LTO.cpp | 9 +- llvm/lib/LTO/ThinLTOCodeGenerator.cpp | 5 +- llvm/lib/Transforms/IPO/FunctionImport.cpp | 97 +++++++--------- llvm/lib/Transforms/IPO/LowerTypeTests.cpp | 2 +- llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp | 2 +- llvm/tools/llvm-link/llvm-link.cpp | 2 +- llvm/tools/llvm-lto/llvm-lto.cpp | 2 +- 14 files changed, 210 insertions(+), 223 deletions(-) diff --git a/clang/lib/CodeGen/BackendUtil.cpp b/clang/lib/CodeGen/BackendUtil.cpp index 0388380..fb1f4fc 100644 --- a/clang/lib/CodeGen/BackendUtil.cpp +++ b/clang/lib/CodeGen/BackendUtil.cpp @@ -975,9 +975,9 @@ static void runThinLTOBackend(ModuleSummaryIndex *CombinedIndex, Module *M, FunctionImporter::ImportMapTy ImportList; for (auto &GlobalList : *CombinedIndex) { auto GUID = GlobalList.first; - assert(GlobalList.second.size() == 1 && + assert(GlobalList.second.SummaryList.size() == 1 && "Expected individual combined index to have one summary per GUID"); - auto &Summary = GlobalList.second[0]; + auto &Summary = GlobalList.second.SummaryList[0]; // Skip the summaries for the importing module. These are included to // e.g. record required linkage changes. if (Summary->modulePath() == M->getModuleIdentifier()) diff --git a/llvm/include/llvm/IR/ModuleSummaryIndex.h b/llvm/include/llvm/IR/ModuleSummaryIndex.h index a7274fb..53570bd 100644 --- a/llvm/include/llvm/IR/ModuleSummaryIndex.h +++ b/llvm/include/llvm/IR/ModuleSummaryIndex.h @@ -45,58 +45,54 @@ struct CalleeInfo { } }; -/// Struct to hold value either by GUID or GlobalValue*. Values in combined -/// indexes as well as indirect calls are GUIDs, all others are GlobalValues. -struct ValueInfo { - /// The value representation used in this instance. - enum ValueInfoKind { - VI_GUID, - VI_Value, - }; +class GlobalValueSummary; - /// Union of the two possible value types. - union ValueUnion { - GlobalValue::GUID Id; - const GlobalValue *GV; - ValueUnion(GlobalValue::GUID Id) : Id(Id) {} - ValueUnion(const GlobalValue *GV) : GV(GV) {} - }; +typedef std::vector> GlobalValueSummaryList; - /// The value being represented. - ValueUnion TheValue; - /// The value representation. - ValueInfoKind Kind; - /// Constructor for a GUID value - ValueInfo(GlobalValue::GUID Id = 0) : TheValue(Id), Kind(VI_GUID) {} - /// Constructor for a GlobalValue* value - ValueInfo(const GlobalValue *V) : TheValue(V), Kind(VI_Value) {} - /// Accessor for GUID value - GlobalValue::GUID getGUID() const { - assert(Kind == VI_GUID && "Not a GUID type"); - return TheValue.Id; - } - /// Accessor for GlobalValue* value - const GlobalValue *getValue() const { - assert(Kind == VI_Value && "Not a Value type"); - return TheValue.GV; - } - bool isGUID() const { return Kind == VI_GUID; } +struct GlobalValueSummaryInfo { + /// The GlobalValue corresponding to this summary. This is only used in + /// per-module summaries. + const GlobalValue *GV = nullptr; + + /// List of global value summary structures for a particular value held + /// in the GlobalValueMap. Requires a vector in the case of multiple + /// COMDAT values of the same name. + GlobalValueSummaryList SummaryList; }; -template <> struct DenseMapInfo { - static inline ValueInfo getEmptyKey() { return ValueInfo((GlobalValue *)-1); } - static inline ValueInfo getTombstoneKey() { - return ValueInfo((GlobalValue *)-2); +/// Map from global value GUID to corresponding summary structures. Use a +/// std::map rather than a DenseMap so that pointers to the map's value_type +/// (which are used by ValueInfo) are not invalidated by insertion. Also it will +/// likely incur less overhead, as the value type is not very small and the size +/// of the map is unknown, resulting in inefficiencies due to repeated +/// insertions and resizing. +typedef std::map + GlobalValueSummaryMapTy; + +/// Struct that holds a reference to a particular GUID in a global value +/// summary. +struct ValueInfo { + const GlobalValueSummaryMapTy::value_type *Ref = nullptr; + ValueInfo() = default; + ValueInfo(const GlobalValueSummaryMapTy::value_type *Ref) : Ref(Ref) {} + operator bool() const { return Ref; } + + GlobalValue::GUID getGUID() const { return Ref->first; } + const GlobalValue *getValue() const { return Ref->second.GV; } + ArrayRef> getSummaryList() const { + return Ref->second.SummaryList; } - static bool isEqual(ValueInfo L, ValueInfo R) { - if (L.isGUID() != R.isGUID()) - return false; - return L.isGUID() ? (L.getGUID() == R.getGUID()) - : (L.getValue() == R.getValue()); +}; + +template <> struct DenseMapInfo { + static inline ValueInfo getEmptyKey() { + return ValueInfo((GlobalValueSummaryMapTy::value_type *)-1); } - static unsigned getHashValue(ValueInfo I) { - return I.isGUID() ? I.getGUID() : (uintptr_t)I.getValue(); + static inline ValueInfo getTombstoneKey() { + return ValueInfo((GlobalValueSummaryMapTy::value_type *)-2); } + static bool isEqual(ValueInfo L, ValueInfo R) { return L.Ref == R.Ref; } + static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.Ref; } }; /// \brief Function and variable summary information to aid decisions and @@ -483,19 +479,6 @@ struct TypeIdSummary { /// 160 bits SHA1 typedef std::array ModuleHash; -/// List of global value summary structures for a particular value held -/// in the GlobalValueMap. Requires a vector in the case of multiple -/// COMDAT values of the same name. -typedef std::vector> GlobalValueSummaryList; - -/// Map from global value GUID to corresponding summary structures. -/// Use a std::map rather than a DenseMap since it will likely incur -/// less overhead, as the value type is not very small and the size -/// of the map is unknown, resulting in inefficiencies due to repeated -/// insertions and resizing. -typedef std::map - GlobalValueSummaryMapTy; - /// Type used for iterating through the global value summary map. typedef GlobalValueSummaryMapTy::const_iterator const_gvsummary_iterator; typedef GlobalValueSummaryMapTy::iterator gvsummary_iterator; @@ -532,6 +515,11 @@ private: // YAML I/O support. friend yaml::MappingTraits; + GlobalValueSummaryMapTy::value_type * + getOrInsertValuePtr(GlobalValue::GUID GUID) { + return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo{}).first; + } + public: gvsummary_iterator begin() { return GlobalValueMap.begin(); } const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); } @@ -539,21 +527,22 @@ public: const_gvsummary_iterator end() const { return GlobalValueMap.end(); } size_t size() const { return GlobalValueMap.size(); } - /// Get the list of global value summary objects for a given value name. - const GlobalValueSummaryList &getGlobalValueSummaryList(StringRef ValueName) { - return GlobalValueMap[GlobalValue::getGUID(ValueName)]; + /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo(). + ValueInfo getValueInfo(GlobalValue::GUID GUID) const { + auto I = GlobalValueMap.find(GUID); + return ValueInfo(I == GlobalValueMap.end() ? nullptr : &*I); } - /// Get the list of global value summary objects for a given value name. - const const_gvsummary_iterator - findGlobalValueSummaryList(StringRef ValueName) const { - return GlobalValueMap.find(GlobalValue::getGUID(ValueName)); + /// Return a ValueInfo for \p GUID. + ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) { + return ValueInfo(getOrInsertValuePtr(GUID)); } - /// Get the list of global value summary objects for a given value GUID. - const const_gvsummary_iterator - findGlobalValueSummaryList(GlobalValue::GUID ValueGUID) const { - return GlobalValueMap.find(ValueGUID); + /// Return a ValueInfo for \p GV and mark it as belonging to GV. + ValueInfo getOrInsertValueInfo(const GlobalValue *GV) { + auto VP = getOrInsertValuePtr(GV->getGUID()); + VP->second.GV = GV; + return ValueInfo(VP); } /// Return the GUID for \p OriginalId in the OidGuidMap. @@ -565,17 +554,18 @@ public: /// Add a global value summary for a value of the given name. void addGlobalValueSummary(StringRef ValueName, std::unique_ptr Summary) { - addOriginalName(GlobalValue::getGUID(ValueName), - Summary->getOriginalName()); - GlobalValueMap[GlobalValue::getGUID(ValueName)].push_back( - std::move(Summary)); + addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)), + std::move(Summary)); } - /// Add a global value summary for a value of the given GUID. - void addGlobalValueSummary(GlobalValue::GUID ValueGUID, + /// Add a global value summary for the given ValueInfo. + void addGlobalValueSummary(ValueInfo VI, std::unique_ptr Summary) { - addOriginalName(ValueGUID, Summary->getOriginalName()); - GlobalValueMap[ValueGUID].push_back(std::move(Summary)); + addOriginalName(VI.getGUID(), Summary->getOriginalName()); + // Here we have a notionally const VI, but the value it points to is owned + // by the non-const *this. + const_cast(VI.Ref) + ->second.SummaryList.push_back(std::move(Summary)); } /// Add an original name for the value of the given GUID. @@ -593,16 +583,16 @@ public: /// not found. GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID, StringRef ModuleId) const { - auto CalleeInfoList = findGlobalValueSummaryList(ValueGUID); - if (CalleeInfoList == end()) { + auto CalleeInfo = getValueInfo(ValueGUID); + if (!CalleeInfo) { return nullptr; // This function does not have a summary } auto Summary = - llvm::find_if(CalleeInfoList->second, + llvm::find_if(CalleeInfo.getSummaryList(), [&](const std::unique_ptr &Summary) { return Summary->modulePath() == ModuleId; }); - if (Summary == CalleeInfoList->second.end()) + if (Summary == CalleeInfo.getSummaryList().end()) return nullptr; return Summary->get(); } diff --git a/llvm/include/llvm/IR/ModuleSummaryIndexYAML.h b/llvm/include/llvm/IR/ModuleSummaryIndexYAML.h index 80719c69..78fdb60 100644 --- a/llvm/include/llvm/IR/ModuleSummaryIndexYAML.h +++ b/llvm/include/llvm/IR/ModuleSummaryIndexYAML.h @@ -201,7 +201,7 @@ template <> struct CustomMappingTraits { for (auto &FSum : FSums) { GlobalValueSummary::GVFlags GVFlags(GlobalValue::ExternalLinkage, false, false); - Elem.push_back(llvm::make_unique( + Elem.SummaryList.push_back(llvm::make_unique( GVFlags, 0, ArrayRef{}, ArrayRef{}, std::move(FSum.TypeTests), std::move(FSum.TypeTestAssumeVCalls), @@ -213,7 +213,7 @@ template <> struct CustomMappingTraits { static void output(IO &io, GlobalValueSummaryMapTy &V) { for (auto &P : V) { std::vector FSums; - for (auto &Sum : P.second) { + for (auto &Sum : P.second.SummaryList) { if (auto *FSum = dyn_cast(Sum.get())) FSums.push_back(FunctionSummaryYaml{ FSum->type_tests(), FSum->type_test_assume_vcalls(), diff --git a/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp b/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp index a8341250..99f900a 100644 --- a/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp +++ b/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp @@ -37,7 +37,8 @@ using namespace llvm; // 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(const User *CurUser, SetVector &RefEdges, +static void findRefEdges(ModuleSummaryIndex &Index, const User *CurUser, + SetVector &RefEdges, SmallPtrSet &Visited) { SmallVector Worklist; Worklist.push_back(CurUser); @@ -61,7 +62,7 @@ static void findRefEdges(const User *CurUser, SetVector &RefEdges, // the reference set unless it is a callee. Callees are handled // specially by WriteFunction and are added to a separate list. if (!(CS && CS.isCallee(&OI))) - RefEdges.insert(GV); + RefEdges.insert(Index.getOrInsertValueInfo(GV)); continue; } Worklist.push_back(Operand); @@ -198,7 +199,7 @@ computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, if (isa(I)) continue; ++NumInsts; - findRefEdges(&I, RefEdges, Visited); + findRefEdges(Index, &I, RefEdges, Visited); auto CS = ImmutableCallSite(&I); if (!CS) continue; @@ -239,7 +240,9 @@ computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, // to record the call edge to the alias in that case. Eventually // an alias summary will be created to associate the alias and // aliasee. - CallGraphEdges[cast(CalledValue)].updateHotness(Hotness); + CallGraphEdges[Index.getOrInsertValueInfo( + cast(CalledValue))] + .updateHotness(Hotness); } else { // Skip inline assembly calls. if (CI && CI->isInlineAsm()) @@ -254,15 +257,16 @@ computeFunctionSummary(ModuleSummaryIndex &Index, const Module &M, ICallAnalysis.getPromotionCandidatesForInstruction( &I, NumVals, TotalCount, NumCandidates); for (auto &Candidate : CandidateProfileData) - CallGraphEdges[Candidate.Value].updateHotness( - getHotness(Candidate.Count, PSI)); + CallGraphEdges[Index.getOrInsertValueInfo(Candidate.Value)] + .updateHotness(getHotness(Candidate.Count, PSI)); } } // Explicit add hot edges to enforce importing for designated GUIDs for // sample PGO, to enable the same inlines as the profiled optimized binary. for (auto &I : F.getImportGUIDs()) - CallGraphEdges[I].updateHotness(CalleeInfo::HotnessType::Hot); + CallGraphEdges[Index.getOrInsertValueInfo(I)].updateHotness( + CalleeInfo::HotnessType::Hot); bool NonRenamableLocal = isNonRenamableLocal(F); bool NotEligibleForImport = @@ -288,7 +292,7 @@ computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V, DenseSet &CantBePromoted) { SetVector RefEdges; SmallPtrSet Visited; - findRefEdges(&V, RefEdges, Visited); + findRefEdges(Index, &V, RefEdges, Visited); bool NonRenamableLocal = isNonRenamableLocal(V); GlobalValueSummary::GVFlags Flags(V.getLinkage(), NonRenamableLocal, /* LiveRoot = */ false); @@ -317,12 +321,9 @@ computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A, // Set LiveRoot flag on entries matching the given value name. static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) { - auto SummaryList = - Index.findGlobalValueSummaryList(GlobalValue::getGUID(Name)); - if (SummaryList == Index.end()) - return; - for (auto &Summary : SummaryList->second) - Summary->setLiveRoot(); + if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name))) + for (auto &Summary : VI.getSummaryList()) + Summary->setLiveRoot(); } ModuleSummaryIndex llvm::buildModuleSummaryIndex( @@ -446,12 +447,16 @@ ModuleSummaryIndex llvm::buildModuleSummaryIndex( } for (auto &GlobalList : Index) { - assert(GlobalList.second.size() == 1 && + // Ignore entries for references that are undefined in the current module. + if (GlobalList.second.SummaryList.empty()) + continue; + + assert(GlobalList.second.SummaryList.size() == 1 && "Expected module's index to have one summary per GUID"); - auto &Summary = GlobalList.second[0]; + auto &Summary = GlobalList.second.SummaryList[0]; bool AllRefsCanBeExternallyReferenced = llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) { - return !CantBePromoted.count(VI.getValue()->getGUID()); + return !CantBePromoted.count(VI.getGUID()); }); if (!AllRefsCanBeExternallyReferenced) { Summary->setNotEligibleToImport(); @@ -461,9 +466,7 @@ ModuleSummaryIndex llvm::buildModuleSummaryIndex( if (auto *FuncSummary = dyn_cast(Summary.get())) { bool AllCallsCanBeExternallyReferenced = llvm::all_of( FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) { - auto GUID = Edge.first.isGUID() ? Edge.first.getGUID() - : Edge.first.getValue()->getGUID(); - return !CantBePromoted.count(GUID); + return !CantBePromoted.count(Edge.first.getGUID()); }); if (!AllCallsCanBeExternallyReferenced) Summary->setNotEligibleToImport(); diff --git a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp index 8b6f79a..580261a 100644 --- a/llvm/lib/Bitcode/Reader/BitcodeReader.cpp +++ b/llvm/lib/Bitcode/Reader/BitcodeReader.cpp @@ -694,15 +694,16 @@ class ModuleSummaryIndexBitcodeReader : public BitcodeReaderBase { /// Used to enable on-demand parsing of the VST. uint64_t VSTOffset = 0; - // Map to save ValueId to GUID association that was recorded in the + // Map to save ValueId to ValueInfo association that was recorded in the // ValueSymbolTable. It is used after the VST is parsed to convert // call graph edges read from the function summary from referencing - // callees by their ValueId to using the GUID instead, which is how + // callees by their ValueId to using the ValueInfo instead, which is how // they are recorded in the summary index being built. - // We save a second GUID which is the same as the first one, but ignoring the - // linkage, i.e. for value other than local linkage they are identical. - DenseMap> - ValueIdToCallGraphGUIDMap; + // We save a GUID which refers to the same global as the ValueInfo, but + // ignoring the linkage, i.e. for values other than local linkage they are + // identical. + DenseMap> + ValueIdToValueInfoMap; /// Map populated during module path string table parsing, from the /// module ID to a string reference owned by the index's module @@ -742,8 +743,8 @@ private: Error parseEntireSummary(); Error parseModuleStringTable(); - std::pair - getGUIDFromValueId(unsigned ValueId); + std::pair + getValueInfoFromValueId(unsigned ValueId); ModulePathStringTableTy::iterator addThisModulePath(); }; @@ -4697,11 +4698,11 @@ ModuleSummaryIndexBitcodeReader::addThisModulePath() { return TheIndex.addModulePath(ModulePath, ModuleId); } -std::pair -ModuleSummaryIndexBitcodeReader::getGUIDFromValueId(unsigned ValueId) { - auto VGI = ValueIdToCallGraphGUIDMap.find(ValueId); - assert(VGI != ValueIdToCallGraphGUIDMap.end()); - return VGI->second; +std::pair +ModuleSummaryIndexBitcodeReader::getValueInfoFromValueId(unsigned ValueId) { + auto VGI = ValueIdToValueInfoMap[ValueId]; + assert(VGI.first); + return VGI; } void ModuleSummaryIndexBitcodeReader::setValueGUID( @@ -4716,8 +4717,8 @@ void ModuleSummaryIndexBitcodeReader::setValueGUID( if (PrintSummaryGUIDs) dbgs() << "GUID " << ValueGUID << "(" << OriginalNameID << ") is " << ValueName << "\n"; - ValueIdToCallGraphGUIDMap[ValueID] = - std::make_pair(ValueGUID, OriginalNameID); + ValueIdToValueInfoMap[ValueID] = + std::make_pair(TheIndex.getOrInsertValueInfo(ValueGUID), OriginalNameID); } // Specialized value symbol table parser used when reading module index @@ -4795,7 +4796,8 @@ Error ModuleSummaryIndexBitcodeReader::parseValueSymbolTable( GlobalValue::GUID RefGUID = Record[1]; // The "original name", which is the second value of the pair will be // overriden later by a FS_COMBINED_ORIGINAL_NAME in the combined index. - ValueIdToCallGraphGUIDMap[ValueID] = std::make_pair(RefGUID, RefGUID); + ValueIdToValueInfoMap[ValueID] = + std::make_pair(TheIndex.getOrInsertValueInfo(RefGUID), RefGUID); break; } } @@ -4940,7 +4942,7 @@ ModuleSummaryIndexBitcodeReader::makeRefList(ArrayRef Record) { std::vector Ret; Ret.reserve(Record.size()); for (uint64_t RefValueId : Record) - Ret.push_back(getGUIDFromValueId(RefValueId).first); + Ret.push_back(getValueInfoFromValueId(RefValueId).first); return Ret; } @@ -4950,14 +4952,14 @@ std::vector ModuleSummaryIndexBitcodeReader::makeCallLi Ret.reserve(Record.size()); for (unsigned I = 0, E = Record.size(); I != E; ++I) { CalleeInfo::HotnessType Hotness = CalleeInfo::HotnessType::Unknown; - GlobalValue::GUID CalleeGUID = getGUIDFromValueId(Record[I]).first; + ValueInfo Callee = getValueInfoFromValueId(Record[I]).first; if (IsOldProfileFormat) { I += 1; // Skip old callsitecount field if (HasProfile) I += 1; // Skip old profilecount field } else if (HasProfile) Hotness = static_cast(Record[++I]); - Ret.push_back(FunctionSummary::EdgeTy{CalleeGUID, CalleeInfo{Hotness}}); + Ret.push_back(FunctionSummary::EdgeTy{Callee, CalleeInfo{Hotness}}); } return Ret; } @@ -5027,7 +5029,8 @@ Error ModuleSummaryIndexBitcodeReader::parseEntireSummary() { case bitc::FS_VALUE_GUID: { // [valueid, refguid] uint64_t ValueID = Record[0]; GlobalValue::GUID RefGUID = Record[1]; - ValueIdToCallGraphGUIDMap[ValueID] = std::make_pair(RefGUID, RefGUID); + ValueIdToValueInfoMap[ValueID] = + std::make_pair(TheIndex.getOrInsertValueInfo(RefGUID), RefGUID); break; } // FS_PERMODULE: [valueid, flags, instcount, numrefs, numrefs x valueid, @@ -5068,10 +5071,10 @@ Error ModuleSummaryIndexBitcodeReader::parseEntireSummary() { PendingTypeCheckedLoadVCalls.clear(); PendingTypeTestAssumeConstVCalls.clear(); PendingTypeCheckedLoadConstVCalls.clear(); - auto GUID = getGUIDFromValueId(ValueID); + auto VIAndOriginalGUID = getValueInfoFromValueId(ValueID); FS->setModulePath(addThisModulePath()->first()); - FS->setOriginalName(GUID.second); - TheIndex.addGlobalValueSummary(GUID.first, std::move(FS)); + FS->setOriginalName(VIAndOriginalGUID.second); + TheIndex.addGlobalValueSummary(VIAndOriginalGUID.first, std::move(FS)); break; } // FS_ALIAS: [valueid, flags, valueid] @@ -5091,14 +5094,15 @@ Error ModuleSummaryIndexBitcodeReader::parseEntireSummary() { // ownership. AS->setModulePath(addThisModulePath()->first()); - GlobalValue::GUID AliaseeGUID = getGUIDFromValueId(AliaseeID).first; + GlobalValue::GUID AliaseeGUID = + getValueInfoFromValueId(AliaseeID).first.getGUID(); auto AliaseeInModule = TheIndex.findSummaryInModule(AliaseeGUID, ModulePath); if (!AliaseeInModule) return error("Alias expects aliasee summary to be parsed"); AS->setAliasee(AliaseeInModule); - auto GUID = getGUIDFromValueId(ValueID); + auto GUID = getValueInfoFromValueId(ValueID); AS->setOriginalName(GUID.second); TheIndex.addGlobalValueSummary(GUID.first, std::move(AS)); break; @@ -5112,7 +5116,7 @@ Error ModuleSummaryIndexBitcodeReader::parseEntireSummary() { makeRefList(ArrayRef(Record).slice(2)); auto FS = llvm::make_unique(Flags, std::move(Refs)); FS->setModulePath(addThisModulePath()->first()); - auto GUID = getGUIDFromValueId(ValueID); + auto GUID = getValueInfoFromValueId(ValueID); FS->setOriginalName(GUID.second); TheIndex.addGlobalValueSummary(GUID.first, std::move(FS)); break; @@ -5139,7 +5143,7 @@ Error ModuleSummaryIndexBitcodeReader::parseEntireSummary() { std::vector Edges = makeCallList( ArrayRef(Record).slice(CallGraphEdgeStartIndex), IsOldProfileFormat, HasProfile); - GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first; + ValueInfo VI = getValueInfoFromValueId(ValueID).first; auto FS = llvm::make_unique( Flags, InstCount, std::move(Refs), std::move(Edges), std::move(PendingTypeTests), std::move(PendingTypeTestAssumeVCalls), @@ -5152,9 +5156,9 @@ Error ModuleSummaryIndexBitcodeReader::parseEntireSummary() { PendingTypeTestAssumeConstVCalls.clear(); PendingTypeCheckedLoadConstVCalls.clear(); LastSeenSummary = FS.get(); - LastSeenGUID = GUID; + LastSeenGUID = VI.getGUID(); FS->setModulePath(ModuleIdMap[ModuleId]); - TheIndex.addGlobalValueSummary(GUID, std::move(FS)); + TheIndex.addGlobalValueSummary(VI, std::move(FS)); break; } // FS_COMBINED_ALIAS: [valueid, modid, flags, valueid] @@ -5170,16 +5174,17 @@ Error ModuleSummaryIndexBitcodeReader::parseEntireSummary() { LastSeenSummary = AS.get(); AS->setModulePath(ModuleIdMap[ModuleId]); - auto AliaseeGUID = getGUIDFromValueId(AliaseeValueId).first; + auto AliaseeGUID = + getValueInfoFromValueId(AliaseeValueId).first.getGUID(); auto AliaseeInModule = TheIndex.findSummaryInModule(AliaseeGUID, AS->modulePath()); if (!AliaseeInModule) return error("Alias expects aliasee summary to be parsed"); AS->setAliasee(AliaseeInModule); - GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first; - LastSeenGUID = GUID; - TheIndex.addGlobalValueSummary(GUID, std::move(AS)); + ValueInfo VI = getValueInfoFromValueId(ValueID).first; + LastSeenGUID = VI.getGUID(); + TheIndex.addGlobalValueSummary(VI, std::move(AS)); break; } // FS_COMBINED_GLOBALVAR_INIT_REFS: [valueid, modid, flags, n x valueid] @@ -5193,9 +5198,9 @@ Error ModuleSummaryIndexBitcodeReader::parseEntireSummary() { auto FS = llvm::make_unique(Flags, std::move(Refs)); LastSeenSummary = FS.get(); FS->setModulePath(ModuleIdMap[ModuleId]); - GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first; - LastSeenGUID = GUID; - TheIndex.addGlobalValueSummary(GUID, std::move(FS)); + ValueInfo VI = getValueInfoFromValueId(ValueID).first; + LastSeenGUID = VI.getGUID(); + TheIndex.addGlobalValueSummary(VI, std::move(FS)); break; } // FS_COMBINED_ORIGINAL_NAME: [original_name] diff --git a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp index 485d9b6..1b8d81a 100644 --- a/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp +++ b/llvm/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -156,14 +156,14 @@ public: return; for (const auto &GUIDSummaryLists : *Index) // Examine all summaries for this GUID. - for (auto &Summary : GUIDSummaryLists.second) + for (auto &Summary : GUIDSummaryLists.second.SummaryList) if (auto FS = dyn_cast(Summary.get())) // For each call in the function summary, see if the call // is to a GUID (which means it is for an indirect call, // otherwise we would have a Value for it). If so, synthesize // a value id. for (auto &CallEdge : FS->calls()) - if (CallEdge.first.isGUID()) + if (!CallEdge.first.getValue()) assignValueId(CallEdge.first.getGUID()); } @@ -304,7 +304,7 @@ private: } // Helper to get the valueId for the type of value recorded in VI. unsigned getValueId(ValueInfo VI) { - if (VI.isGUID()) + if (!VI.getValue()) return getValueId(VI.getGUID()); return VE.getValueID(VI.getValue()); } @@ -358,7 +358,7 @@ public: Callback(Summary); } else { for (auto &Summaries : Index) - for (auto &Summary : Summaries.second) + for (auto &Summary : Summaries.second.SummaryList) Callback({Summaries.first, Summary.get()}); } } @@ -3270,15 +3270,14 @@ void ModuleBitcodeWriter::writePerModuleFunctionSummaryRecord( void ModuleBitcodeWriter::writeModuleLevelReferences( const GlobalVariable &V, SmallVector &NameVals, unsigned FSModRefsAbbrev) { - auto Summaries = - Index->findGlobalValueSummaryList(GlobalValue::getGUID(V.getName())); - if (Summaries == Index->end()) { + auto VI = Index->getValueInfo(GlobalValue::getGUID(V.getName())); + if (!VI || VI.getSummaryList().empty()) { // Only declarations should not have a summary (a declaration might however // have a summary if the def was in module level asm). assert(V.isDeclaration()); return; } - auto *Summary = Summaries->second.front().get(); + auto *Summary = VI.getSummaryList()[0].get(); NameVals.push_back(VE.getValueID(&V)); GlobalVarSummary *VS = cast(Summary); NameVals.push_back(getEncodedGVSummaryFlags(VS->flags())); @@ -3367,15 +3366,14 @@ void ModuleBitcodeWriter::writePerModuleGlobalValueSummary() { if (!F.hasName()) report_fatal_error("Unexpected anonymous function when writing summary"); - auto Summaries = - Index->findGlobalValueSummaryList(GlobalValue::getGUID(F.getName())); - if (Summaries == Index->end()) { + ValueInfo VI = Index->getValueInfo(GlobalValue::getGUID(F.getName())); + if (!VI || VI.getSummaryList().empty()) { // Only declarations should not have a summary (a declaration might // however have a summary if the def was in module level asm). assert(F.isDeclaration()); continue; } - auto *Summary = Summaries->second.front().get(); + auto *Summary = VI.getSummaryList()[0].get(); writePerModuleFunctionSummaryRecord(NameVals, Summary, VE.getValueID(&F), FSCallsAbbrev, FSCallsProfileAbbrev, F); } diff --git a/llvm/lib/IR/ModuleSummaryIndex.cpp b/llvm/lib/IR/ModuleSummaryIndex.cpp index 01e1b81..9dd712f 100644 --- a/llvm/lib/IR/ModuleSummaryIndex.cpp +++ b/llvm/lib/IR/ModuleSummaryIndex.cpp @@ -22,7 +22,7 @@ void ModuleSummaryIndex::collectDefinedFunctionsForModule( StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const { for (auto &GlobalList : *this) { auto GUID = GlobalList.first; - for (auto &GlobSummary : GlobalList.second) { + for (auto &GlobSummary : GlobalList.second.SummaryList) { auto *Summary = dyn_cast_or_null(GlobSummary.get()); if (!Summary) // Ignore global variable, focus on functions @@ -40,7 +40,7 @@ void ModuleSummaryIndex::collectDefinedGVSummariesPerModule( StringMap &ModuleToDefinedGVSummaries) const { for (auto &GlobalList : *this) { auto GUID = GlobalList.first; - for (auto &Summary : GlobalList.second) { + for (auto &Summary : GlobalList.second.SummaryList) { ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get(); } } @@ -49,10 +49,10 @@ void ModuleSummaryIndex::collectDefinedGVSummariesPerModule( GlobalValueSummary * ModuleSummaryIndex::getGlobalValueSummary(uint64_t ValueGUID, bool PerModuleIndex) const { - auto SummaryList = findGlobalValueSummaryList(ValueGUID); - assert(SummaryList != end() && "GlobalValue not found in index"); - assert((!PerModuleIndex || SummaryList->second.size() == 1) && + auto VI = getValueInfo(ValueGUID); + assert(VI && "GlobalValue not found in index"); + assert((!PerModuleIndex || VI.getSummaryList().size() == 1) && "Expected a single entry per global value in per-module index"); - auto &Summary = SummaryList->second[0]; + auto &Summary = VI.getSummaryList()[0]; return Summary.get(); } diff --git a/llvm/lib/LTO/LTO.cpp b/llvm/lib/LTO/LTO.cpp index 0afa1ba..2d2dcde 100644 --- a/llvm/lib/LTO/LTO.cpp +++ b/llvm/lib/LTO/LTO.cpp @@ -274,13 +274,14 @@ void llvm::thinLTOResolveWeakForLinkerInIndex( // when needed. DenseSet GlobalInvolvedWithAlias; for (auto &I : Index) - for (auto &S : I.second) + for (auto &S : I.second.SummaryList) if (auto AS = dyn_cast(S.get())) GlobalInvolvedWithAlias.insert(&AS->getAliasee()); for (auto &I : Index) - thinLTOResolveWeakForLinkerGUID(I.second, I.first, GlobalInvolvedWithAlias, - isPrevailing, recordNewLinkage); + thinLTOResolveWeakForLinkerGUID(I.second.SummaryList, I.first, + GlobalInvolvedWithAlias, isPrevailing, + recordNewLinkage); } static void thinLTOInternalizeAndPromoteGUID( @@ -301,7 +302,7 @@ void llvm::thinLTOInternalizeAndPromoteInIndex( ModuleSummaryIndex &Index, function_ref isExported) { for (auto &I : Index) - thinLTOInternalizeAndPromoteGUID(I.second, I.first, isExported); + thinLTOInternalizeAndPromoteGUID(I.second.SummaryList, I.first, isExported); } // Requires a destructor for std::vector. diff --git a/llvm/lib/LTO/ThinLTOCodeGenerator.cpp b/llvm/lib/LTO/ThinLTOCodeGenerator.cpp index 440275c..b4ee7c2 100644 --- a/llvm/lib/LTO/ThinLTOCodeGenerator.cpp +++ b/llvm/lib/LTO/ThinLTOCodeGenerator.cpp @@ -119,8 +119,9 @@ static void computePrevailingCopies( }; for (auto &I : Index) { - if (HasMultipleCopies(I.second)) - PrevailingCopy[I.first] = getFirstDefinitionForLinker(I.second); + if (HasMultipleCopies(I.second.SummaryList)) + PrevailingCopy[I.first] = + getFirstDefinitionForLinker(I.second.SummaryList); } } diff --git a/llvm/lib/Transforms/IPO/FunctionImport.cpp b/llvm/lib/Transforms/IPO/FunctionImport.cpp index c7ef249..7ed07d6 100644 --- a/llvm/lib/Transforms/IPO/FunctionImport.cpp +++ b/llvm/lib/Transforms/IPO/FunctionImport.cpp @@ -117,7 +117,7 @@ namespace { /// - [insert you fancy metric here] static const GlobalValueSummary * selectCallee(const ModuleSummaryIndex &Index, - const GlobalValueSummaryList &CalleeSummaryList, + ArrayRef> CalleeSummaryList, unsigned Threshold, StringRef CallerModulePath) { auto It = llvm::find_if( CalleeSummaryList, @@ -168,19 +168,6 @@ selectCallee(const ModuleSummaryIndex &Index, return cast(It->get()); } -/// Return the summary for the function \p GUID that fits the \p Threshold, or -/// null if there's no match. -static const GlobalValueSummary *selectCallee(GlobalValue::GUID GUID, - unsigned Threshold, - const ModuleSummaryIndex &Index, - StringRef CallerModulePath) { - auto CalleeSummaryList = Index.findGlobalValueSummaryList(GUID); - if (CalleeSummaryList == Index.end()) - return nullptr; // This function does not have a summary - return selectCallee(Index, CalleeSummaryList->second, Threshold, - CallerModulePath); -} - using EdgeInfo = std::tuple; @@ -194,19 +181,23 @@ static void computeImportForFunction( FunctionImporter::ImportMapTy &ImportList, StringMap *ExportLists = nullptr) { for (auto &Edge : Summary.calls()) { - auto GUID = Edge.first.getGUID(); - DEBUG(dbgs() << " edge -> " << GUID << " Threshold:" << Threshold << "\n"); + ValueInfo VI = Edge.first; + DEBUG(dbgs() << " edge -> " << VI.getGUID() << " Threshold:" << Threshold + << "\n"); - if (Index.findGlobalValueSummaryList(GUID) == Index.end()) { + if (VI.getSummaryList().empty()) { // For SamplePGO, the indirect call targets for local functions will // have its original name annotated in profile. We try to find the // corresponding PGOFuncName as the GUID. - GUID = Index.getGUIDFromOriginalID(GUID); + auto GUID = Index.getGUIDFromOriginalID(VI.getGUID()); if (GUID == 0) continue; + VI = Index.getValueInfo(GUID); + if (!VI) + continue; } - if (DefinedGVSummaries.count(GUID)) { + if (DefinedGVSummaries.count(VI.getGUID())) { DEBUG(dbgs() << "ignored! Target already in destination module.\n"); continue; } @@ -222,8 +213,8 @@ static void computeImportForFunction( const auto NewThreshold = Threshold * GetBonusMultiplier(Edge.second.Hotness); - auto *CalleeSummary = - selectCallee(GUID, NewThreshold, Index, Summary.modulePath()); + auto *CalleeSummary = selectCallee(Index, VI.getSummaryList(), NewThreshold, + Summary.modulePath()); if (!CalleeSummary) { DEBUG(dbgs() << "ignored! No qualifying callee with summary found.\n"); continue; @@ -255,7 +246,7 @@ static void computeImportForFunction( const auto AdjThreshold = GetAdjustedThreshold(Threshold, IsHotCallsite); auto ExportModulePath = ResolvedCalleeSummary->modulePath(); - auto &ProcessedThreshold = ImportList[ExportModulePath][GUID]; + auto &ProcessedThreshold = ImportList[ExportModulePath][VI.getGUID()]; /// Since the traversal of the call graph is DFS, we can revisit a function /// a second time with a higher threshold. In this case, it is added back to /// the worklist with the new threshold. @@ -271,7 +262,7 @@ static void computeImportForFunction( // Make exports in the source module. if (ExportLists) { auto &ExportList = (*ExportLists)[ExportModulePath]; - ExportList.insert(GUID); + ExportList.insert(VI.getGUID()); if (!PreviouslyImported) { // This is the first time this function was exported from its source // module, so mark all functions and globals it references as exported @@ -291,7 +282,7 @@ static void computeImportForFunction( } // Insert the newly imported function to the worklist. - Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, GUID); + Worklist.emplace_back(ResolvedCalleeSummary, AdjThreshold, VI.getGUID()); } } @@ -431,57 +422,56 @@ DenseSet llvm::computeDeadSymbols( if (GUIDPreservedSymbols.empty()) // Don't do anything when nothing is live, this is friendly with tests. return DenseSet(); - DenseSet LiveSymbols = GUIDPreservedSymbols; - SmallVector Worklist; - Worklist.reserve(LiveSymbols.size() * 2); - for (auto GUID : LiveSymbols) { - DEBUG(dbgs() << "Live root: " << GUID << "\n"); - Worklist.push_back(GUID); + DenseSet LiveSymbols; + SmallVector Worklist; + Worklist.reserve(GUIDPreservedSymbols.size() * 2); + for (auto GUID : GUIDPreservedSymbols) { + ValueInfo VI = Index.getValueInfo(GUID); + if (!VI) + continue; + DEBUG(dbgs() << "Live root: " << VI.getGUID() << "\n"); + LiveSymbols.insert(VI); + Worklist.push_back(VI); } // Add values flagged in the index as live roots to the worklist. for (const auto &Entry : Index) { bool IsLiveRoot = llvm::any_of( - Entry.second, + Entry.second.SummaryList, [&](const std::unique_ptr &Summary) { return Summary->liveRoot(); }); if (!IsLiveRoot) continue; DEBUG(dbgs() << "Live root (summary): " << Entry.first << "\n"); - Worklist.push_back(Entry.first); + Worklist.push_back(ValueInfo(&Entry)); } while (!Worklist.empty()) { - auto GUID = Worklist.pop_back_val(); - auto It = Index.findGlobalValueSummaryList(GUID); - if (It == Index.end()) { - DEBUG(dbgs() << "Not in index: " << GUID << "\n"); - continue; - } + auto VI = Worklist.pop_back_val(); // FIXME: we should only make the prevailing copy live here - for (auto &Summary : It->second) { + for (auto &Summary : VI.getSummaryList()) { for (auto Ref : Summary->refs()) { - auto RefGUID = Ref.getGUID(); - if (LiveSymbols.insert(RefGUID).second) { - DEBUG(dbgs() << "Marking live (ref): " << RefGUID << "\n"); - Worklist.push_back(RefGUID); + if (LiveSymbols.insert(Ref).second) { + DEBUG(dbgs() << "Marking live (ref): " << Ref.getGUID() << "\n"); + Worklist.push_back(Ref); } } if (auto *FS = dyn_cast(Summary.get())) { for (auto Call : FS->calls()) { - auto CallGUID = Call.first.getGUID(); - if (LiveSymbols.insert(CallGUID).second) { - DEBUG(dbgs() << "Marking live (call): " << CallGUID << "\n"); - Worklist.push_back(CallGUID); + if (LiveSymbols.insert(Call.first).second) { + DEBUG(dbgs() << "Marking live (call): " << Call.first.getGUID() + << "\n"); + Worklist.push_back(Call.first); } } } if (auto *AS = dyn_cast(Summary.get())) { auto AliaseeGUID = AS->getAliasee().getOriginalName(); - if (LiveSymbols.insert(AliaseeGUID).second) { + ValueInfo AliaseeVI = Index.getValueInfo(AliaseeGUID); + if (AliaseeVI && LiveSymbols.insert(AliaseeVI).second) { DEBUG(dbgs() << "Marking live (alias): " << AliaseeGUID << "\n"); - Worklist.push_back(AliaseeGUID); + Worklist.push_back(AliaseeVI); } } } @@ -490,10 +480,9 @@ DenseSet llvm::computeDeadSymbols( DeadSymbols.reserve( std::min(Index.size(), Index.size() - LiveSymbols.size())); for (auto &Entry : Index) { - auto GUID = Entry.first; - if (!LiveSymbols.count(GUID)) { - DEBUG(dbgs() << "Marking dead: " << GUID << "\n"); - DeadSymbols.insert(GUID); + if (!LiveSymbols.count(ValueInfo(&Entry))) { + DEBUG(dbgs() << "Marking dead: " << Entry.first << "\n"); + DeadSymbols.insert(Entry.first); } } DEBUG(dbgs() << LiveSymbols.size() << " symbols Live, and " @@ -825,7 +814,7 @@ static bool doImportingForModule(Module &M) { // is only enabled when testing importing via the 'opt' tool, which does // not do the ThinLink that would normally determine what values to promote. for (auto &I : *Index) { - for (auto &S : I.second) { + for (auto &S : I.second.SummaryList) { if (GlobalValue::isLocalLinkage(S->linkage())) S->setLinkage(GlobalValue::ExternalLinkage); } diff --git a/llvm/lib/Transforms/IPO/LowerTypeTests.cpp b/llvm/lib/Transforms/IPO/LowerTypeTests.cpp index 785207e..ca4ee92 100644 --- a/llvm/lib/Transforms/IPO/LowerTypeTests.cpp +++ b/llvm/lib/Transforms/IPO/LowerTypeTests.cpp @@ -1440,7 +1440,7 @@ bool LowerTypeTestsModule::lower() { } for (auto &P : *ExportSummary) { - for (auto &S : P.second) { + for (auto &S : P.second.SummaryList) { auto *FS = dyn_cast(S.get()); if (!FS) continue; diff --git a/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp b/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp index cb7d487..aae22c5 100644 --- a/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp +++ b/llvm/lib/Transforms/IPO/WholeProgramDevirt.cpp @@ -1322,7 +1322,7 @@ bool DevirtModule::run() { } for (auto &P : *ExportSummary) { - for (auto &S : P.second) { + for (auto &S : P.second.SummaryList) { auto *FS = dyn_cast(S.get()); if (!FS) continue; diff --git a/llvm/tools/llvm-link/llvm-link.cpp b/llvm/tools/llvm-link/llvm-link.cpp index 27199d5..568e5f8 100644 --- a/llvm/tools/llvm-link/llvm-link.cpp +++ b/llvm/tools/llvm-link/llvm-link.cpp @@ -300,7 +300,7 @@ static bool linkFiles(const char *argv0, LLVMContext &Context, Linker &L, // does not do the ThinLink that would normally determine what values to // promote. for (auto &I : *Index) { - for (auto &S : I.second) { + for (auto &S : I.second.SummaryList) { if (GlobalValue::isLocalLinkage(S->linkage())) S->setLinkage(GlobalValue::ExternalLinkage); } diff --git a/llvm/tools/llvm-lto/llvm-lto.cpp b/llvm/tools/llvm-lto/llvm-lto.cpp index 27e5c5e..2458d3d 100644 --- a/llvm/tools/llvm-lto/llvm-lto.cpp +++ b/llvm/tools/llvm-lto/llvm-lto.cpp @@ -284,7 +284,7 @@ void printIndexStats() { unsigned Calls = 0, Refs = 0, Functions = 0, Alias = 0, Globals = 0; for (auto &Summaries : *Index) { - for (auto &Summary : Summaries.second) { + for (auto &Summary : Summaries.second.SummaryList) { Refs += Summary->refs().size(); if (auto *FuncSummary = dyn_cast(Summary.get())) { Functions++; -- 2.7.4