diff options
Diffstat (limited to 'include/llvm/IR/ModuleSummaryIndex.h')
| -rw-r--r-- | include/llvm/IR/ModuleSummaryIndex.h | 453 |
1 files changed, 390 insertions, 63 deletions
diff --git a/include/llvm/IR/ModuleSummaryIndex.h b/include/llvm/IR/ModuleSummaryIndex.h index dd7a0db83774..fdf3d4b5f1ce 100644 --- a/include/llvm/IR/ModuleSummaryIndex.h +++ b/include/llvm/IR/ModuleSummaryIndex.h @@ -25,6 +25,10 @@ #include "llvm/ADT/StringRef.h" #include "llvm/IR/GlobalValue.h" #include "llvm/IR/Module.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/ScaledNumber.h" +#include "llvm/Support/StringSaver.h" #include <algorithm> #include <array> #include <cassert> @@ -45,7 +49,7 @@ template <typename T> struct MappingTraits; } // end namespace yaml -/// \brief Class to accumulate and hold information about a callee. +/// Class to accumulate and hold information about a callee. struct CalleeInfo { enum class HotnessType : uint8_t { Unknown = 0, @@ -54,13 +58,44 @@ struct CalleeInfo { Hot = 3, Critical = 4 }; - HotnessType Hotness = HotnessType::Unknown; - CalleeInfo() = default; - explicit CalleeInfo(HotnessType Hotness) : Hotness(Hotness) {} + // The size of the bit-field might need to be adjusted if more values are + // added to HotnessType enum. + uint32_t Hotness : 3; + + /// The value stored in RelBlockFreq has to be interpreted as the digits of + /// a scaled number with a scale of \p -ScaleShift. + uint32_t RelBlockFreq : 29; + static constexpr int32_t ScaleShift = 8; + static constexpr uint64_t MaxRelBlockFreq = (1 << 29) - 1; + + CalleeInfo() + : Hotness(static_cast<uint32_t>(HotnessType::Unknown)), RelBlockFreq(0) {} + explicit CalleeInfo(HotnessType Hotness, uint64_t RelBF) + : Hotness(static_cast<uint32_t>(Hotness)), RelBlockFreq(RelBF) {} void updateHotness(const HotnessType OtherHotness) { - Hotness = std::max(Hotness, OtherHotness); + Hotness = std::max(Hotness, static_cast<uint32_t>(OtherHotness)); + } + + HotnessType getHotness() const { return HotnessType(Hotness); } + + /// Update \p RelBlockFreq from \p BlockFreq and \p EntryFreq + /// + /// BlockFreq is divided by EntryFreq and added to RelBlockFreq. To represent + /// fractional values, the result is represented as a fixed point number with + /// scale of -ScaleShift. + void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq) { + if (EntryFreq == 0) + return; + using Scaled64 = ScaledNumber<uint64_t>; + Scaled64 Temp(BlockFreq, ScaleShift); + Temp /= Scaled64::get(EntryFreq); + + uint64_t Sum = + SaturatingAdd<uint64_t>(Temp.toInt<uint64_t>(), RelBlockFreq); + Sum = std::min(Sum, uint64_t(MaxRelBlockFreq)); + RelBlockFreq = static_cast<uint32_t>(Sum); } }; @@ -69,9 +104,29 @@ class GlobalValueSummary; using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>; struct GlobalValueSummaryInfo { - /// The GlobalValue corresponding to this summary. This is only used in - /// per-module summaries. - const GlobalValue *GV = nullptr; + union NameOrGV { + NameOrGV(bool HaveGVs) { + if (HaveGVs) + GV = nullptr; + else + Name = ""; + } + + /// The GlobalValue corresponding to this summary. This is only used in + /// per-module summaries and when the IR is available. E.g. when module + /// analysis is being run, or when parsing both the IR and the summary + /// from assembly. + const GlobalValue *GV; + + /// Summary string representation. This StringRef points to BC module + /// string table and is valid until module data is stored in memory. + /// This is guaranteed to happen until runThinLTOBackend function is + /// called, so it is safe to use this field during thin link. This field + /// is only valid if summary index was loaded from BC file. + StringRef Name; + } U; + + GlobalValueSummaryInfo(bool HaveGVs) : U(HaveGVs) {} /// List of global value summary structures for a particular value held /// in the GlobalValueMap. Requires a vector in the case of multiple @@ -91,44 +146,98 @@ using GlobalValueSummaryMapTy = /// Struct that holds a reference to a particular GUID in a global value /// summary. struct ValueInfo { - const GlobalValueSummaryMapTy::value_type *Ref = nullptr; + PointerIntPair<const GlobalValueSummaryMapTy::value_type *, 1, bool> + RefAndFlag; ValueInfo() = default; - ValueInfo(const GlobalValueSummaryMapTy::value_type *Ref) : Ref(Ref) {} + ValueInfo(bool HaveGVs, const GlobalValueSummaryMapTy::value_type *R) { + RefAndFlag.setPointer(R); + RefAndFlag.setInt(HaveGVs); + } - operator bool() const { return Ref; } + operator bool() const { return getRef(); } - GlobalValue::GUID getGUID() const { return Ref->first; } - const GlobalValue *getValue() const { return Ref->second.GV; } + GlobalValue::GUID getGUID() const { return getRef()->first; } + const GlobalValue *getValue() const { + assert(haveGVs()); + return getRef()->second.U.GV; + } ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const { - return Ref->second.SummaryList; + return getRef()->second.SummaryList; + } + + StringRef name() const { + return haveGVs() ? getRef()->second.U.GV->getName() + : getRef()->second.U.Name; + } + + bool haveGVs() const { return RefAndFlag.getInt(); } + + const GlobalValueSummaryMapTy::value_type *getRef() const { + return RefAndFlag.getPointer(); } + + bool isDSOLocal() const; }; +inline raw_ostream &operator<<(raw_ostream &OS, const ValueInfo &VI) { + OS << VI.getGUID(); + if (!VI.name().empty()) + OS << " (" << VI.name() << ")"; + return OS; +} + +inline bool operator==(const ValueInfo &A, const ValueInfo &B) { + assert(A.getRef() && B.getRef() && + "Need ValueInfo with non-null Ref for comparison"); + return A.getRef() == B.getRef(); +} + +inline bool operator!=(const ValueInfo &A, const ValueInfo &B) { + assert(A.getRef() && B.getRef() && + "Need ValueInfo with non-null Ref for comparison"); + return A.getRef() != B.getRef(); +} + +inline bool operator<(const ValueInfo &A, const ValueInfo &B) { + assert(A.getRef() && B.getRef() && + "Need ValueInfo with non-null Ref to compare GUIDs"); + return A.getGUID() < B.getGUID(); +} + template <> struct DenseMapInfo<ValueInfo> { static inline ValueInfo getEmptyKey() { - return ValueInfo((GlobalValueSummaryMapTy::value_type *)-1); + return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8); } static inline ValueInfo getTombstoneKey() { - return ValueInfo((GlobalValueSummaryMapTy::value_type *)-2); + return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-16); + } + + static inline bool isSpecialKey(ValueInfo V) { + return V == getTombstoneKey() || V == getEmptyKey(); } - static bool isEqual(ValueInfo L, ValueInfo R) { return L.Ref == R.Ref; } - static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.Ref; } + static bool isEqual(ValueInfo L, ValueInfo R) { + // We are not supposed to mix ValueInfo(s) with different HaveGVs flag + // in a same container. + assert(isSpecialKey(L) || isSpecialKey(R) || (L.haveGVs() == R.haveGVs())); + return L.getRef() == R.getRef(); + } + static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); } }; -/// \brief Function and variable summary information to aid decisions and +/// Function and variable summary information to aid decisions and /// implementation of importing. class GlobalValueSummary { public: - /// \brief Sububclass discriminator (for dyn_cast<> et al.) + /// Sububclass discriminator (for dyn_cast<> et al.) enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind }; /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield. struct GVFlags { - /// \brief The linkage type of the associated global value. + /// The linkage type of the associated global value. /// /// One use is to flag values that have local linkage types and need to /// have module identifier appended before placing into the combined @@ -170,7 +279,7 @@ private: /// GUID includes the module level id in the hash. GlobalValue::GUID OriginalName = 0; - /// \brief Path of module IR containing value's definition, used to locate + /// Path of module IR containing value's definition, used to locate /// module during importing. /// /// This is only used during parsing of the combined index, or when @@ -185,8 +294,6 @@ private: /// are listed in the derived FunctionSummary object. std::vector<ValueInfo> RefEdgeList; - bool isLive() const { return Flags.Live; } - protected: GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs) : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) { @@ -199,7 +306,7 @@ public: /// Returns the hash of the original name, it is identical to the GUID for /// externally visible symbols, but not for local ones. - GlobalValue::GUID getOriginalName() { return OriginalName; } + GlobalValue::GUID getOriginalName() const { return OriginalName; } /// Initialize the original name hash in this summary. void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; } @@ -215,7 +322,7 @@ public: StringRef modulePath() const { return ModulePath; } /// Get the flags for this GlobalValue (see \p struct GVFlags). - GVFlags flags() { return Flags; } + GVFlags flags() const { return Flags; } /// Return linkage type recorded for this global value. GlobalValue::LinkageTypes linkage() const { @@ -231,6 +338,8 @@ public: /// Return true if this global value can't be imported. bool notEligibleToImport() const { return Flags.NotEligibleToImport; } + bool isLive() const { return Flags.Live; } + void setLive(bool Live) { Flags.Live = Live; } void setDSOLocal(bool Local) { Flags.DSOLocal = Local; } @@ -249,11 +358,9 @@ public: const GlobalValueSummary *getBaseObject() const; friend class ModuleSummaryIndex; - friend void computeDeadSymbols(class ModuleSummaryIndex &, - const DenseSet<GlobalValue::GUID> &); }; -/// \brief Alias summary information. +/// Alias summary information. class AliasSummary : public GlobalValueSummary { GlobalValueSummary *AliaseeSummary; // AliaseeGUID is only set and accessed when we are building a combined index @@ -273,6 +380,8 @@ public: void setAliasee(GlobalValueSummary *Aliasee) { AliaseeSummary = Aliasee; } void setAliaseeGUID(GlobalValue::GUID GUID) { AliaseeGUID = GUID; } + bool hasAliasee() const { return !!AliaseeSummary; } + const GlobalValueSummary &getAliasee() const { assert(AliaseeSummary && "Unexpected missing aliasee summary"); return *AliaseeSummary; @@ -300,13 +409,20 @@ inline GlobalValueSummary *GlobalValueSummary::getBaseObject() { return this; } -/// \brief Function summary information to aid decisions and implementation of +/// Function summary information to aid decisions and implementation of /// importing. class FunctionSummary : public GlobalValueSummary { public: /// <CalleeValueInfo, CalleeInfo> call edge pair. using EdgeTy = std::pair<ValueInfo, CalleeInfo>; + /// Types for -force-summary-edges-cold debugging option. + enum ForceSummaryHotnessType : unsigned { + FSHT_None, + FSHT_AllNonCritical, + FSHT_All + }; + /// An "identifier" for a virtual function. This contains the type identifier /// represented as a GUID and the offset from the address point to the virtual /// function pointer, where "address point" is as defined in the Itanium ABI: @@ -324,6 +440,26 @@ public: std::vector<uint64_t> Args; }; + /// All type identifier related information. Because these fields are + /// relatively uncommon we only allocate space for them if necessary. + struct TypeIdInfo { + /// List of type identifiers used by this function in llvm.type.test + /// intrinsics referenced by something other than an llvm.assume intrinsic, + /// represented as GUIDs. + std::vector<GlobalValue::GUID> TypeTests; + + /// List of virtual calls made by this function using (respectively) + /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do + /// not have all constant integer arguments. + std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls; + + /// List of virtual calls made by this function using (respectively) + /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with + /// all constant integer arguments. + std::vector<ConstVCall> TypeTestAssumeConstVCalls, + TypeCheckedLoadConstVCalls; + }; + /// Function attribute flags. Used to track if a function accesses memory, /// recurses or aliases. struct FFlags { @@ -333,6 +469,25 @@ public: unsigned ReturnDoesNotAlias : 1; }; + /// Create an empty FunctionSummary (with specified call edges). + /// Used to represent external nodes and the dummy root node. + static FunctionSummary + makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) { + return FunctionSummary( + FunctionSummary::GVFlags( + GlobalValue::LinkageTypes::AvailableExternallyLinkage, + /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false), + 0, FunctionSummary::FFlags{}, std::vector<ValueInfo>(), + std::move(Edges), std::vector<GlobalValue::GUID>(), + std::vector<FunctionSummary::VFuncId>(), + std::vector<FunctionSummary::VFuncId>(), + std::vector<FunctionSummary::ConstVCall>(), + std::vector<FunctionSummary::ConstVCall>()); + } + + /// 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. @@ -345,25 +500,6 @@ private: /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function. std::vector<EdgeTy> CallGraphEdgeList; - /// All type identifier related information. Because these fields are - /// relatively uncommon we only allocate space for them if necessary. - struct TypeIdInfo { - /// List of type identifiers used by this function in llvm.type.test - /// intrinsics other than by an llvm.assume intrinsic, represented as GUIDs. - std::vector<GlobalValue::GUID> TypeTests; - - /// List of virtual calls made by this function using (respectively) - /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do - /// not have all constant integer arguments. - std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls; - - /// List of virtual calls made by this function using (respectively) - /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with - /// all constant integer arguments. - std::vector<ConstVCall> TypeTestAssumeConstVCalls, - TypeCheckedLoadConstVCalls; - }; - std::unique_ptr<TypeIdInfo> TIdInfo; public: @@ -393,7 +529,7 @@ public: } /// Get function attribute flags. - FFlags &fflags() { return FunFlags; } + FFlags fflags() const { return FunFlags; } /// Get the instruction count recorded for this function. unsigned instCount() const { return InstCount; } @@ -452,6 +588,10 @@ public: TIdInfo = llvm::make_unique<TypeIdInfo>(); TIdInfo->TypeTests.push_back(Guid); } + + const TypeIdInfo *getTypeIdInfo() const { return TIdInfo.get(); }; + + friend struct GraphTraits<ValueInfo>; }; template <> struct DenseMapInfo<FunctionSummary::VFuncId> { @@ -488,7 +628,7 @@ template <> struct DenseMapInfo<FunctionSummary::ConstVCall> { } }; -/// \brief Global variable summary information to aid decisions and +/// Global variable summary information to aid decisions and /// implementation of importing. /// /// Currently this doesn't add anything to the base \p GlobalValueSummary, @@ -538,8 +678,11 @@ struct TypeTestResolution { struct WholeProgramDevirtResolution { enum Kind { - Indir, ///< Just do a regular virtual call - SingleImpl, ///< Single implementation devirtualization + Indir, ///< Just do a regular virtual call + SingleImpl, ///< Single implementation devirtualization + BranchFunnel, ///< When retpoline mitigation is enabled, use a branch funnel + ///< that is defined in the merged module. Otherwise same as + ///< Indir. } TheKind = Indir; std::string SingleImplName; @@ -607,7 +750,6 @@ private: /// Mapping from type identifiers to summary information for that type /// identifier. - // FIXME: Add bitcode read/write support for this field. std::map<std::string, TypeIdSummary> TypeIdMap; /// Mapping from original ID to GUID. If original ID can map to multiple @@ -619,24 +761,111 @@ private: /// considered live. bool WithGlobalValueDeadStripping = false; + /// Indicates that distributed backend should skip compilation of the + /// module. Flag is suppose to be set by distributed ThinLTO indexing + /// when it detected that the module is not needed during the final + /// linking. As result distributed backend should just output a minimal + /// valid object file. + bool SkipModuleByDistributedBackend = false; + + /// If true then we're performing analysis of IR module, or parsing along with + /// the IR from assembly. The value of 'false' means we're reading summary + /// from BC or YAML source. Affects the type of value stored in NameOrGV + /// union. + bool HaveGVs; + std::set<std::string> CfiFunctionDefs; std::set<std::string> CfiFunctionDecls; + // Used in cases where we want to record the name of a global, but + // don't have the string owned elsewhere (e.g. the Strtab on a module). + StringSaver Saver; + BumpPtrAllocator Alloc; + // YAML I/O support. friend yaml::MappingTraits<ModuleSummaryIndex>; GlobalValueSummaryMapTy::value_type * getOrInsertValuePtr(GlobalValue::GUID GUID) { - return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo{}).first; + return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs)) + .first; } public: + // See HaveGVs variable comment. + ModuleSummaryIndex(bool HaveGVs) : HaveGVs(HaveGVs), Saver(Alloc) {} + + bool haveGVs() const { return HaveGVs; } + gvsummary_iterator begin() { return GlobalValueMap.begin(); } const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); } gvsummary_iterator end() { return GlobalValueMap.end(); } const_gvsummary_iterator end() const { return GlobalValueMap.end(); } size_t size() const { return GlobalValueMap.size(); } + /// Convenience function for doing a DFS on a ValueInfo. Marks the function in + /// the FunctionHasParent map. + static void discoverNodes(ValueInfo V, + std::map<ValueInfo, bool> &FunctionHasParent) { + if (!V.getSummaryList().size()) + return; // skip external functions that don't have summaries + + // Mark discovered if we haven't yet + auto S = FunctionHasParent.emplace(V, false); + + // Stop if we've already discovered this node + if (!S.second) + return; + + FunctionSummary *F = + dyn_cast<FunctionSummary>(V.getSummaryList().front().get()); + assert(F != nullptr && "Expected FunctionSummary node"); + + for (auto &C : F->calls()) { + // Insert node if necessary + auto S = FunctionHasParent.emplace(C.first, true); + + // Skip nodes that we're sure have parents + if (!S.second && S.first->second) + continue; + + if (S.second) + discoverNodes(C.first, FunctionHasParent); + else + S.first->second = true; + } + } + + // Calculate the callgraph root + FunctionSummary calculateCallGraphRoot() { + // Functions that have a parent will be marked in FunctionHasParent pair. + // Once we've marked all functions, the functions in the map that are false + // have no parent (so they're the roots) + std::map<ValueInfo, bool> FunctionHasParent; + + for (auto &S : *this) { + // Skip external functions + if (!S.second.SummaryList.size() || + !isa<FunctionSummary>(S.second.SummaryList.front().get())) + continue; + discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent); + } + + std::vector<FunctionSummary::EdgeTy> Edges; + // create edges to all roots in the Index + for (auto &P : FunctionHasParent) { + if (P.second) + continue; // skip over non-root nodes + Edges.push_back(std::make_pair(P.first, CalleeInfo{})); + } + if (Edges.empty()) { + // Failed to find root - return an empty node + return FunctionSummary::makeDummyFunctionSummary({}); + } + auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges); + return CallGraphRoot; + } + bool withGlobalValueDeadStripping() const { return WithGlobalValueDeadStripping; } @@ -644,27 +873,54 @@ public: WithGlobalValueDeadStripping = true; } + bool skipModuleByDistributedBackend() const { + return SkipModuleByDistributedBackend; + } + void setSkipModuleByDistributedBackend() { + SkipModuleByDistributedBackend = true; + } + bool isGlobalValueLive(const GlobalValueSummary *GVS) const { return !WithGlobalValueDeadStripping || GVS->isLive(); } bool isGUIDLive(GlobalValue::GUID GUID) const; + /// Return a ValueInfo for the index value_type (convenient when iterating + /// index). + ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const { + return ValueInfo(HaveGVs, &R); + } + /// 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); + return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I); } /// Return a ValueInfo for \p GUID. ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) { - return ValueInfo(getOrInsertValuePtr(GUID)); + return ValueInfo(HaveGVs, getOrInsertValuePtr(GUID)); + } + + // Save a string in the Index. Use before passing Name to + // getOrInsertValueInfo when the string isn't owned elsewhere (e.g. on the + // module's Strtab). + StringRef saveString(std::string String) { return Saver.save(String); } + + /// Return a ValueInfo for \p GUID setting value \p Name. + ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name) { + assert(!HaveGVs); + auto VP = getOrInsertValuePtr(GUID); + VP->second.U.Name = Name; + return ValueInfo(HaveGVs, VP); } /// Return a ValueInfo for \p GV and mark it as belonging to GV. ValueInfo getOrInsertValueInfo(const GlobalValue *GV) { + assert(HaveGVs); auto VP = getOrInsertValuePtr(GV->getGUID()); - VP->second.GV = GV; - return ValueInfo(VP); + VP->second.U.GV = GV; + return ValueInfo(HaveGVs, VP); } /// Return the GUID for \p OriginalId in the OidGuidMap. @@ -679,6 +935,12 @@ public: std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; } const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; } + /// Add a global value summary for a value. + void addGlobalValueSummary(const GlobalValue &GV, + std::unique_ptr<GlobalValueSummary> Summary) { + addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary)); + } + /// Add a global value summary for a value of the given name. void addGlobalValueSummary(StringRef ValueName, std::unique_ptr<GlobalValueSummary> Summary) { @@ -692,7 +954,7 @@ public: 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<GlobalValueSummaryMapTy::value_type *>(VI.Ref) + const_cast<GlobalValueSummaryMapTy::value_type *>(VI.getRef()) ->second.SummaryList.push_back(std::move(Summary)); } @@ -730,8 +992,7 @@ public: GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV, bool PerModuleIndex = true) const { assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name"); - return getGlobalValueSummary(GlobalValue::getGUID(GV.getName()), - PerModuleIndex); + return getGlobalValueSummary(GV.getGUID(), PerModuleIndex); } /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that @@ -788,6 +1049,13 @@ public: return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first; } + /// Return module entry for module with the given \p ModPath. + ModuleInfo *getModule(StringRef ModPath) { + auto It = ModulePathStringTable.find(ModPath); + assert(It != ModulePathStringTable.end() && "Module not registered"); + return &*It; + } + /// Check if the given Module has any functions available for exporting /// in the index. We consider any module present in the ModulePathStringTable /// to have exported functions. @@ -814,7 +1082,7 @@ public: return &I->second; } - /// Collect for the given module the list of function it defines + /// Collect for the given module the list of functions it defines /// (GUID -> Summary). void collectDefinedFunctionsForModule(StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const; @@ -823,6 +1091,65 @@ public: /// Summary). void collectDefinedGVSummariesPerModule( StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const; + + /// Print to an output stream. + void print(raw_ostream &OS, bool IsForDebug = false) const; + + /// Dump to stderr (for debugging). + void dump() const; + + /// Export summary to dot file for GraphViz. + void exportToDot(raw_ostream& OS) const; + + /// Print out strongly connected components for debugging. + void dumpSCCs(raw_ostream &OS); +}; + +/// GraphTraits definition to build SCC for the index +template <> struct GraphTraits<ValueInfo> { + typedef ValueInfo NodeRef; + + static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) { + return P.first; + } + using ChildIteratorType = + mapped_iterator<std::vector<FunctionSummary::EdgeTy>::iterator, + decltype(&valueInfoFromEdge)>; + + static NodeRef getEntryNode(ValueInfo V) { return V; } + + static ChildIteratorType child_begin(NodeRef N) { + if (!N.getSummaryList().size()) // handle external function + return ChildIteratorType( + FunctionSummary::ExternalNode.CallGraphEdgeList.begin(), + &valueInfoFromEdge); + FunctionSummary *F = + cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject()); + return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge); + } + + static ChildIteratorType child_end(NodeRef N) { + if (!N.getSummaryList().size()) // handle external function + return ChildIteratorType( + FunctionSummary::ExternalNode.CallGraphEdgeList.end(), + &valueInfoFromEdge); + FunctionSummary *F = + cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject()); + return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge); + } +}; + +template <> +struct GraphTraits<ModuleSummaryIndex *> : public GraphTraits<ValueInfo> { + static NodeRef getEntryNode(ModuleSummaryIndex *I) { + std::unique_ptr<GlobalValueSummary> Root = + make_unique<FunctionSummary>(I->calculateCallGraphRoot()); + GlobalValueSummaryInfo G(I->haveGVs()); + G.SummaryList.push_back(std::move(Root)); + static auto P = + GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G)); + return ValueInfo(I->haveGVs(), &P); + } }; } // end namespace llvm |