Index: llvm/include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- llvm/include/llvm/IR/ModuleSummaryIndex.h +++ llvm/include/llvm/IR/ModuleSummaryIndex.h @@ -41,8 +41,8 @@ } }; -/// Struct to hold value either by GUID or Value*, depending on whether this -/// is a combined or per-module index, respectively. +/// 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 { @@ -53,9 +53,9 @@ /// Union of the two possible value types. union ValueUnion { GlobalValue::GUID Id; - const Value *V; + const GlobalValue *GV; ValueUnion(GlobalValue::GUID Id) : Id(Id) {} - ValueUnion(const Value *V) : V(V) {} + ValueUnion(const GlobalValue *GV) : GV(GV) {} }; /// The value being represented. @@ -64,21 +64,37 @@ ValueInfoKind Kind; /// Constructor for a GUID value ValueInfo(GlobalValue::GUID Id = 0) : TheValue(Id), Kind(VI_GUID) {} - /// Constructor for a Value* value - ValueInfo(const Value *V) : TheValue(V), Kind(VI_Value) {} + /// 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 Value* value - const Value *getValue() const { + /// Accessor for GlobalValue* value + const GlobalValue *getValue() const { assert(Kind == VI_Value && "Not a Value type"); - return TheValue.V; + return TheValue.GV; } bool isGUID() const { return Kind == VI_GUID; } }; +template <> struct DenseMapInfo { + static inline ValueInfo getEmptyKey() { return ValueInfo((GlobalValue *)-1); } + static inline ValueInfo getTombstoneKey() { + return ValueInfo((GlobalValue *)-2); + } + 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()); + } + static unsigned getHashValue(ValueInfo I) { + return I.isGUID() ? I.getGUID() : (uintptr_t)I.getValue(); + } +}; + /// \brief Function and variable summary information to aid decisions and /// implementation of importing. class GlobalValueSummary { @@ -156,11 +172,12 @@ /// (either by the initializer of a global variable, or referenced /// from within a function). This does not include functions called, which /// are listed in the derived FunctionSummary object. - std::vector RefEdgeList; + OwningArrayRef RefEdgeList; protected: /// GlobalValueSummary constructor. - GlobalValueSummary(SummaryKind K, GVFlags Flags) : Kind(K), Flags(Flags) {} + GlobalValueSummary(SummaryKind K, GVFlags Flags, ArrayRef Refs) + : Kind(K), Flags(Flags), RefEdgeList(Refs) {} public: virtual ~GlobalValueSummary() = default; @@ -222,24 +239,8 @@ Flags.HasInlineAsmMaybeReferencingInternal = true; } - /// Record a reference from this global value to the global value identified - /// by \p RefGUID. - void addRefEdge(GlobalValue::GUID RefGUID) { RefEdgeList.push_back(RefGUID); } - - /// Record a reference from this global value to the global value identified - /// by \p RefV. - void addRefEdge(const Value *RefV) { RefEdgeList.push_back(RefV); } - - /// Record a reference from this global value to each global value identified - /// in \p RefEdges. - void addRefEdges(DenseSet &RefEdges) { - for (auto &RI : RefEdges) - addRefEdge(RI); - } - /// Return the list of values referenced by this global value definition. - std::vector &refs() { return RefEdgeList; } - const std::vector &refs() const { return RefEdgeList; } + ArrayRef refs() const { return RefEdgeList; } }; /// \brief Alias summary information. @@ -248,7 +249,8 @@ public: /// Summary constructors. - AliasSummary(GVFlags Flags) : GlobalValueSummary(AliasKind, Flags) {} + AliasSummary(GVFlags Flags, ArrayRef Refs) + : GlobalValueSummary(AliasKind, Flags, Refs) {} /// Check if this is an alias summary. static bool classof(const GlobalValueSummary *GVS) { @@ -280,12 +282,14 @@ unsigned InstCount; /// List of call edge pairs from this function. - std::vector CallGraphEdgeList; + OwningArrayRef CallGraphEdgeList; public: /// Summary constructors. - FunctionSummary(GVFlags Flags, unsigned NumInsts) - : GlobalValueSummary(FunctionKind, Flags), InstCount(NumInsts) {} + FunctionSummary(GVFlags Flags, unsigned NumInsts, ArrayRef Refs, + ArrayRef CGEdges) + : GlobalValueSummary(FunctionKind, Flags, Refs), InstCount(NumInsts), + CallGraphEdgeList(CGEdges) {} /// Check if this is a function summary. static bool classof(const GlobalValueSummary *GVS) { @@ -295,38 +299,8 @@ /// Get the instruction count recorded for this function. unsigned instCount() const { return InstCount; } - /// Record a call graph edge from this function to the function identified - /// by \p CalleeGUID, with \p CalleeInfo including the cumulative profile - /// count (across all calls from this function) or 0 if no PGO. - void addCallGraphEdge(GlobalValue::GUID CalleeGUID, CalleeInfo Info) { - CallGraphEdgeList.push_back(std::make_pair(CalleeGUID, Info)); - } - - /// Record a call graph edge from this function to each function GUID recorded - /// in \p CallGraphEdges. - void - addCallGraphEdges(DenseMap &CallGraphEdges) { - for (auto &EI : CallGraphEdges) - addCallGraphEdge(EI.first, EI.second); - } - - /// Record a call graph edge from this function to the function identified - /// by \p CalleeV, with \p CalleeInfo including the cumulative profile - /// count (across all calls from this function) or 0 if no PGO. - void addCallGraphEdge(const Value *CalleeV, CalleeInfo Info) { - CallGraphEdgeList.push_back(std::make_pair(CalleeV, Info)); - } - - /// Record a call graph edge from this function to each function recorded - /// in \p CallGraphEdges. - void addCallGraphEdges(DenseMap &CallGraphEdges) { - for (auto &EI : CallGraphEdges) - addCallGraphEdge(EI.first, EI.second); - } - /// Return the list of pairs. - std::vector &calls() { return CallGraphEdgeList; } - const std::vector &calls() const { return CallGraphEdgeList; } + ArrayRef calls() const { return CallGraphEdgeList; } }; /// \brief Global variable summary information to aid decisions and @@ -339,7 +313,8 @@ public: /// Summary constructors. - GlobalVarSummary(GVFlags Flags) : GlobalValueSummary(GlobalVarKind, Flags) {} + GlobalVarSummary(GVFlags Flags, ArrayRef Refs) + : GlobalValueSummary(GlobalVarKind, Flags, Refs) {} /// Check if this is a global variable summary. static bool classof(const GlobalValueSummary *GVS) { Index: llvm/lib/Analysis/ModuleSummaryAnalysis.cpp =================================================================== --- llvm/lib/Analysis/ModuleSummaryAnalysis.cpp +++ llvm/lib/Analysis/ModuleSummaryAnalysis.cpp @@ -13,6 +13,8 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/ModuleSummaryAnalysis.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/Triple.h" #include "llvm/Analysis/BlockFrequencyInfo.h" #include "llvm/Analysis/BlockFrequencyInfoImpl.h" @@ -34,7 +36,7 @@ // 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, DenseSet &RefEdges, +static void findRefEdges(const User *CurUser, SetVector &RefEdges, SmallPtrSet &Visited) { SmallVector Worklist; Worklist.push_back(CurUser); @@ -53,12 +55,12 @@ continue; if (isa(Operand)) continue; - if (isa(Operand)) { + if (auto *GV = dyn_cast(Operand)) { // We have a reference to a global value. This should be added to // 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(Operand); + RefEdges.insert(GV); continue; } Worklist.push_back(Operand); @@ -88,9 +90,8 @@ unsigned NumInsts = 0; // Map from callee ValueId to profile count. Used to accumulate profile // counts for all static calls to a given callee. - DenseMap CallGraphEdges; - DenseMap IndirectCallEdges; - DenseSet RefEdges; + MapVector CallGraphEdges; + SetVector RefEdges; ICallPromotionAnalysis ICallAnalysis; bool HasInlineAsmMaybeReferencingInternal = false; @@ -130,16 +131,14 @@ // We should have named any anonymous globals assert(CalledFunction->hasName()); auto ScaledCount = BFI ? BFI->getBlockProfileCount(&BB) : None; + auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI) + : CalleeInfo::HotnessType::Unknown; + // Use the original CalledValue, in case it was an alias. We want // to record the call edge to the alias in that case. Eventually // an alias summary will be created to associate the alias and // aliasee. - auto *CalleeId = - M.getValueSymbolTable().lookup(CalledValue->getName()); - - auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI) - : CalleeInfo::HotnessType::Unknown; - CallGraphEdges[CalleeId].updateHotness(Hotness); + CallGraphEdges[cast(CalledValue)].updateHotness(Hotness); } else { // Skip inline assembly calls. if (CI && CI->isInlineAsm()) @@ -154,17 +153,14 @@ ICallAnalysis.getPromotionCandidatesForInstruction( &I, NumVals, TotalCount, NumCandidates); for (auto &Candidate : CandidateProfileData) - IndirectCallEdges[Candidate.Value].updateHotness( + CallGraphEdges[Candidate.Value].updateHotness( getHotness(Candidate.Count, PSI)); } } GlobalValueSummary::GVFlags Flags(F); - std::unique_ptr FuncSummary = - llvm::make_unique(Flags, NumInsts); - FuncSummary->addCallGraphEdges(CallGraphEdges); - FuncSummary->addCallGraphEdges(IndirectCallEdges); - FuncSummary->addRefEdges(RefEdges); + auto FuncSummary = llvm::make_unique( + Flags, NumInsts, RefEdges.getArrayRef(), CallGraphEdges.getArrayRef()); if (HasInlineAsmMaybeReferencingInternal) FuncSummary->setHasInlineAsmMaybeReferencingInternal(); Index.addGlobalValueSummary(F.getName(), std::move(FuncSummary)); @@ -172,20 +168,19 @@ static void computeVariableSummary(ModuleSummaryIndex &Index, const GlobalVariable &V) { - DenseSet RefEdges; + SetVector RefEdges; SmallPtrSet Visited; findRefEdges(&V, RefEdges, Visited); GlobalValueSummary::GVFlags Flags(V); - std::unique_ptr GVarSummary = - llvm::make_unique(Flags); - GVarSummary->addRefEdges(RefEdges); + auto GVarSummary = + llvm::make_unique(Flags, RefEdges.getArrayRef()); Index.addGlobalValueSummary(V.getName(), std::move(GVarSummary)); } static void computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A) { GlobalValueSummary::GVFlags Flags(A); - std::unique_ptr AS = llvm::make_unique(Flags); + auto AS = llvm::make_unique(Flags, ArrayRef{}); auto *Aliasee = A.getBaseObject(); auto *AliaseeSummary = Index.getGlobalValueSummary(*Aliasee); assert(AliaseeSummary && "Alias expects aliasee summary to be parsed"); @@ -283,12 +278,15 @@ // Create the appropriate summary type. if (isa(GV)) { std::unique_ptr Summary = - llvm::make_unique(GVFlags, 0); + llvm::make_unique( + GVFlags, 0, ArrayRef{}, + ArrayRef{}); Summary->setNoRename(); Index.addGlobalValueSummary(Name, std::move(Summary)); } else { std::unique_ptr Summary = - llvm::make_unique(GVFlags); + llvm::make_unique(GVFlags, + ArrayRef{}); Summary->setNoRename(); Index.addGlobalValueSummary(Name, std::move(Summary)); } Index: llvm/lib/Bitcode/Reader/BitcodeReader.cpp =================================================================== --- llvm/lib/Bitcode/Reader/BitcodeReader.cpp +++ llvm/lib/Bitcode/Reader/BitcodeReader.cpp @@ -668,14 +668,15 @@ Error parseValueSymbolTable( uint64_t Offset, DenseMap &ValueIdToLinkageMap); + std::vector makeRefList(ArrayRef Record); + std::vector makeCallList(ArrayRef Record, + bool IsOldProfileFormat, + bool HasProfile); Error parseEntireSummary(StringRef ModulePath); Error parseModuleStringTable(); - std::pair + std::pair getGUIDFromValueId(unsigned ValueId); - std::pair - readCallGraphEdge(const SmallVector &Record, unsigned int &I, - bool IsOldProfileFormat, bool HasProfile); }; } // end anonymous namespace @@ -4792,6 +4793,33 @@ } } +std::vector +ModuleSummaryIndexBitcodeReader::makeRefList(ArrayRef Record) { + std::vector Ret; + Ret.reserve(Record.size()); + for (uint64_t RefValueId : Record) + Ret.push_back(getGUIDFromValueId(RefValueId).first); + return Ret; +} + +std::vector ModuleSummaryIndexBitcodeReader::makeCallList( + ArrayRef Record, bool IsOldProfileFormat, bool HasProfile) { + std::vector Ret; + 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; + 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}}); + } + return Ret; +} + // Eagerly parse the entire summary block. This populates the GlobalValueSummary // objects in the index. Error ModuleSummaryIndexBitcodeReader::parseEntireSummary( @@ -4868,33 +4896,25 @@ unsigned InstCount = Record[2]; unsigned NumRefs = Record[3]; auto Flags = getDecodedGVSummaryFlags(RawFlags, Version); - std::unique_ptr FS = - llvm::make_unique(Flags, InstCount); // The module path string ref set in the summary must be owned by the // index's module string table. Since we don't have a module path // string table section in the per-module index, we create a single // module path string table entry with an empty (0) ID to take // ownership. - FS->setModulePath(TheIndex.addModulePath(ModulePath, 0)->first()); static int RefListStartIndex = 4; int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs; assert(Record.size() >= RefListStartIndex + NumRefs && "Record size inconsistent with number of references"); - for (unsigned I = 4, E = CallGraphEdgeStartIndex; I != E; ++I) { - unsigned RefValueId = Record[I]; - GlobalValue::GUID RefGUID = getGUIDFromValueId(RefValueId).first; - FS->addRefEdge(RefGUID); - } + std::vector Refs = makeRefList( + ArrayRef(Record).slice(RefListStartIndex, NumRefs)); bool HasProfile = (BitCode == bitc::FS_PERMODULE_PROFILE); - for (unsigned I = CallGraphEdgeStartIndex, E = Record.size(); I != E; - ++I) { - CalleeInfo::HotnessType Hotness; - GlobalValue::GUID CalleeGUID; - std::tie(CalleeGUID, Hotness) = - readCallGraphEdge(Record, I, IsOldProfileFormat, HasProfile); - FS->addCallGraphEdge(CalleeGUID, CalleeInfo(Hotness)); - } + std::vector Calls = makeCallList( + ArrayRef(Record).slice(CallGraphEdgeStartIndex), + IsOldProfileFormat, HasProfile); + auto FS = + llvm::make_unique(Flags, InstCount, Refs, Calls); auto GUID = getGUIDFromValueId(ValueID); + FS->setModulePath(TheIndex.addModulePath(ModulePath, 0)->first()); FS->setOriginalName(GUID.second); TheIndex.addGlobalValueSummary(GUID.first, std::move(FS)); break; @@ -4907,7 +4927,7 @@ uint64_t RawFlags = Record[1]; unsigned AliaseeID = Record[2]; auto Flags = getDecodedGVSummaryFlags(RawFlags, Version); - std::unique_ptr AS = llvm::make_unique(Flags); + auto AS = llvm::make_unique(Flags, ArrayRef{}); // 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 @@ -4931,14 +4951,10 @@ unsigned ValueID = Record[0]; uint64_t RawFlags = Record[1]; auto Flags = getDecodedGVSummaryFlags(RawFlags, Version); - std::unique_ptr FS = - llvm::make_unique(Flags); + std::vector Refs = + makeRefList(ArrayRef(Record).slice(2)); + auto FS = llvm::make_unique(Flags, Refs); FS->setModulePath(TheIndex.addModulePath(ModulePath, 0)->first()); - for (unsigned I = 2, E = Record.size(); I != E; ++I) { - unsigned RefValueId = Record[I]; - GlobalValue::GUID RefGUID = getGUIDFromValueId(RefValueId).first; - FS->addRefEdge(RefGUID); - } auto GUID = getGUIDFromValueId(ValueID); FS->setOriginalName(GUID.second); TheIndex.addGlobalValueSummary(GUID.first, std::move(FS)); @@ -4956,30 +4972,21 @@ unsigned InstCount = Record[3]; unsigned NumRefs = Record[4]; auto Flags = getDecodedGVSummaryFlags(RawFlags, Version); - std::unique_ptr FS = - llvm::make_unique(Flags, InstCount); - LastSeenSummary = FS.get(); - FS->setModulePath(ModuleIdMap[ModuleId]); static int RefListStartIndex = 5; int CallGraphEdgeStartIndex = RefListStartIndex + NumRefs; assert(Record.size() >= RefListStartIndex + NumRefs && "Record size inconsistent with number of references"); - for (unsigned I = RefListStartIndex, E = CallGraphEdgeStartIndex; I != E; - ++I) { - unsigned RefValueId = Record[I]; - GlobalValue::GUID RefGUID = getGUIDFromValueId(RefValueId).first; - FS->addRefEdge(RefGUID); - } + std::vector Refs = makeRefList( + ArrayRef(Record).slice(RefListStartIndex, NumRefs)); bool HasProfile = (BitCode == bitc::FS_COMBINED_PROFILE); - for (unsigned I = CallGraphEdgeStartIndex, E = Record.size(); I != E; - ++I) { - CalleeInfo::HotnessType Hotness; - GlobalValue::GUID CalleeGUID; - std::tie(CalleeGUID, Hotness) = - readCallGraphEdge(Record, I, IsOldProfileFormat, HasProfile); - FS->addCallGraphEdge(CalleeGUID, CalleeInfo(Hotness)); - } + std::vector Edges = makeCallList( + ArrayRef(Record).slice(CallGraphEdgeStartIndex), + IsOldProfileFormat, HasProfile); GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first; + auto FS = + llvm::make_unique(Flags, InstCount, Refs, Edges); + LastSeenSummary = FS.get(); + FS->setModulePath(ModuleIdMap[ModuleId]); TheIndex.addGlobalValueSummary(GUID, std::move(FS)); Combined = true; break; @@ -4993,7 +5000,7 @@ uint64_t RawFlags = Record[2]; unsigned AliaseeValueId = Record[3]; auto Flags = getDecodedGVSummaryFlags(RawFlags, Version); - std::unique_ptr AS = llvm::make_unique(Flags); + auto AS = llvm::make_unique(Flags, ArrayRef{}); LastSeenSummary = AS.get(); AS->setModulePath(ModuleIdMap[ModuleId]); @@ -5015,15 +5022,11 @@ uint64_t ModuleId = Record[1]; uint64_t RawFlags = Record[2]; auto Flags = getDecodedGVSummaryFlags(RawFlags, Version); - std::unique_ptr FS = - llvm::make_unique(Flags); + std::vector Refs = + makeRefList(ArrayRef(Record).slice(3)); + auto FS = llvm::make_unique(Flags, Refs); LastSeenSummary = FS.get(); FS->setModulePath(ModuleIdMap[ModuleId]); - for (unsigned I = 3, E = Record.size(); I != E; ++I) { - unsigned RefValueId = Record[I]; - GlobalValue::GUID RefGUID = getGUIDFromValueId(RefValueId).first; - FS->addRefEdge(RefGUID); - } GlobalValue::GUID GUID = getGUIDFromValueId(ValueID).first; TheIndex.addGlobalValueSummary(GUID, std::move(FS)); Combined = true; @@ -5043,23 +5046,6 @@ llvm_unreachable("Exit infinite loop"); } -std::pair -ModuleSummaryIndexBitcodeReader::readCallGraphEdge( - const SmallVector &Record, unsigned int &I, - const bool IsOldProfileFormat, const bool HasProfile) { - - auto Hotness = CalleeInfo::HotnessType::Unknown; - unsigned CalleeValueId = Record[I]; - GlobalValue::GUID CalleeGUID = getGUIDFromValueId(CalleeValueId).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]); - return {CalleeGUID, Hotness}; -} - // Parse the module string table block into the Index. // This populates the ModulePathStringTable map in the index. Error ModuleSummaryIndexBitcodeReader::parseModuleStringTable() { Index: llvm/lib/Bitcode/Writer/BitcodeWriter.cpp =================================================================== --- llvm/lib/Bitcode/Writer/BitcodeWriter.cpp +++ llvm/lib/Bitcode/Writer/BitcodeWriter.cpp @@ -3275,21 +3275,11 @@ NameVals.push_back(FS->instCount()); NameVals.push_back(FS->refs().size()); - unsigned SizeBeforeRefs = NameVals.size(); for (auto &RI : FS->refs()) NameVals.push_back(VE.getValueID(RI.getValue())); - // Sort the refs for determinism output, the vector returned by FS->refs() has - // been initialized from a DenseSet. - std::sort(NameVals.begin() + SizeBeforeRefs, NameVals.end()); - std::vector Calls = FS->calls(); - std::sort(Calls.begin(), Calls.end(), - [this](const FunctionSummary::EdgeTy &L, - const FunctionSummary::EdgeTy &R) { - return getValueId(L.first) < getValueId(R.first); - }); bool HasProfileData = F.getEntryCount().hasValue(); - for (auto &ECI : Calls) { + for (auto &ECI : FS->calls()) { NameVals.push_back(getValueId(ECI.first)); if (HasProfileData) NameVals.push_back(static_cast(ECI.second.Hotness)); Index: llvm/test/Bitcode/thinlto-function-summary-callgraph-profile-summary.ll =================================================================== --- llvm/test/Bitcode/thinlto-function-summary-callgraph-profile-summary.ll +++ llvm/test/Bitcode/thinlto-function-summary-callgraph-profile-summary.ll @@ -10,7 +10,7 @@ ; CHECK-NEXT: +; CHECK-NEXT: ; CHECK-NEXT: ; CHECK-LABEL: