From c13f8098687a1c8a17c382719e74fe7dbdfc559f Mon Sep 17 00:00:00 2001 From: Charles Saternos Date: Sun, 11 Feb 2018 22:06:20 +0000 Subject: [PATCH] [ThinLTO] Add GraphTraits for FunctionSummaries Add GraphTraits definitions to the FunctionSummary and ModuleSummaryIndex classes. These GraphTraits will be used to construct find SCC's in ThinLTO analysis passes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@324854 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/IR/ModuleSummaryIndex.h | 150 +++++++++++++++++++++++++++++++++- lib/IR/ModuleSummaryIndex.cpp | 24 ++++++ lib/LTO/LTO.cpp | 7 ++ lib/Transforms/IPO/FunctionImport.cpp | 2 +- 4 files changed, 181 insertions(+), 2 deletions(-) diff --git a/include/llvm/IR/ModuleSummaryIndex.h b/include/llvm/IR/ModuleSummaryIndex.h index d75986b37fb..e99b20dca88 100644 --- a/include/llvm/IR/ModuleSummaryIndex.h +++ b/include/llvm/IR/ModuleSummaryIndex.h @@ -162,6 +162,24 @@ struct ValueInfo { bool isDSOLocal() const; }; +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.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(); +} + +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 { static inline ValueInfo getEmptyKey() { return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8); @@ -397,6 +415,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 Edges) { + return FunctionSummary( + FunctionSummary::GVFlags( + GlobalValue::LinkageTypes::AvailableExternallyLinkage, + /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false), + 0, FunctionSummary::FFlags{}, std::vector(), + std::move(Edges), std::vector(), + std::vector(), + std::vector(), + std::vector(), + std::vector()); + } + + /// 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. @@ -516,6 +553,8 @@ public: TIdInfo = llvm::make_unique(); TIdInfo->TypeTests.push_back(Guid); } + + friend struct GraphTraits; }; template <> struct DenseMapInfo { @@ -712,6 +751,65 @@ public: const_gvsummary_iterator end() const { return GlobalValueMap.end(); } size_t size() const { return GlobalValueMap.size(); } + // 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 FunctionHasParent; + std::function discoverNodes = [&](ValueInfo V) { + 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(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); + else + S.first->second = true; + } + }; + + for (auto &S : *this) { + // Skip external functions + if (!S.second.SummaryList.size() || + !isa(S.second.SummaryList.front().get())) + continue; + discoverNodes(ValueInfo(IsAnalysis, &S)); + } + + std::vector 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; } @@ -735,7 +833,7 @@ public: return ValueInfo(IsAnalysis, getOrInsertValuePtr(GUID)); } - /// Return a ValueInfo for \p GUID setting value \p Name. + /// Return a ValueInfo for \p GUID setting value \p Name. ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name) { assert(!IsAnalysis); auto VP = getOrInsertValuePtr(GUID); @@ -910,6 +1008,56 @@ public: /// 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 { + typedef ValueInfo NodeRef; + + static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) { + return P.first; + } + using ChildIteratorType = + mapped_iterator::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(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(N.getSummaryList().front()->getBaseObject()); + return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge); + } +}; + +template <> +struct GraphTraits : public GraphTraits { + static NodeRef getEntryNode(ModuleSummaryIndex *I) { + std::unique_ptr Root = + make_unique(I->calculateCallGraphRoot()); + GlobalValueSummaryInfo G(I->isPerformingAnalysis()); + G.SummaryList.push_back(std::move(Root)); + static auto P = + GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G)); + return ValueInfo(I->isPerformingAnalysis(), &P); + } }; } // end namespace llvm diff --git a/lib/IR/ModuleSummaryIndex.cpp b/lib/IR/ModuleSummaryIndex.cpp index ce74c00766f..4c4466f9a90 100644 --- a/lib/IR/ModuleSummaryIndex.cpp +++ b/lib/IR/ModuleSummaryIndex.cpp @@ -13,10 +13,14 @@ //===----------------------------------------------------------------------===// #include "llvm/IR/ModuleSummaryIndex.h" +#include "llvm/ADT/SCCIterator.h" #include "llvm/ADT/StringMap.h" #include "llvm/Support/Path.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; +FunctionSummary FunctionSummary::ExternalNode = + FunctionSummary::makeDummyFunctionSummary({}); bool ValueInfo::isDSOLocal() const { // Need to check all summaries are local in case of hash collisions. return getSummaryList().size() && @@ -80,6 +84,26 @@ bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const { return false; } +// TODO: write a graphviz dumper for SCCs (see ModuleSummaryIndex::exportToDot) +// then delete this function and update its tests +LLVM_DUMP_METHOD +void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) { + for (scc_iterator I = + scc_begin(this); + !I.isAtEnd(); ++I) { + O << "SCC (" << utostr(I->size()) << " node" << (I->size() == 1 ? "" : "s") + << ") {\n"; + for (const ValueInfo V : *I) { + FunctionSummary *F = nullptr; + if (V.getSummaryList().size()) + F = cast(V.getSummaryList().front().get()); + O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID()) + << (I.hasLoop() ? " (has loop)" : "") << "\n"; + } + O << "}\n"; + } +} + namespace { struct Attributes { void add(const Twine &Name, const Twine &Value, diff --git a/lib/LTO/LTO.cpp b/lib/LTO/LTO.cpp index 1047b8ddeb4..94baee63b0e 100644 --- a/lib/LTO/LTO.cpp +++ b/lib/LTO/LTO.cpp @@ -50,6 +50,10 @@ using namespace object; #define DEBUG_TYPE "lto" +static cl::opt + DumpThinCGSCCs("dump-thin-cg-sccs", cl::init(false), cl::Hidden, + cl::desc("Dump the SCCs in the ThinLTO index's callgraph")); + // The values are (type identifier, summary) pairs. typedef DenseMap< GlobalValue::GUID, @@ -1141,6 +1145,9 @@ Error LTO::runThinLTO(AddStreamFn AddStream, NativeObjectCache Cache) { ThinLTO.ModuleMap.size()); StringMap> ResolvedODR; + if (DumpThinCGSCCs) + ThinLTO.CombinedIndex.dumpSCCs(outs()); + if (Conf.OptLevel > 0) ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries, ImportLists, ExportLists); diff --git a/lib/Transforms/IPO/FunctionImport.cpp b/lib/Transforms/IPO/FunctionImport.cpp index b92f798c4ab..b68058cbeea 100644 --- a/lib/Transforms/IPO/FunctionImport.cpp +++ b/lib/Transforms/IPO/FunctionImport.cpp @@ -18,8 +18,8 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringMap.h" -#include "llvm/ADT/StringSet.h" #include "llvm/ADT/StringRef.h" +#include "llvm/ADT/StringSet.h" #include "llvm/Bitcode/BitcodeReader.h" #include "llvm/IR/AutoUpgrade.h" #include "llvm/IR/Constants.h" -- 2.11.0