Index: include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- include/llvm/IR/ModuleSummaryIndex.h +++ include/llvm/IR/ModuleSummaryIndex.h @@ -162,6 +162,24 @@ 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 @@ 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 @@ TIdInfo = llvm::make_unique(); TIdInfo->TypeTests.push_back(Guid); } + + friend struct GraphTraits; }; template <> struct DenseMapInfo { @@ -718,6 +757,69 @@ 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 &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(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 FunctionHasParent; + + for (auto &S : *this) { + // Skip external functions + if (!S.second.SummaryList.size() || + !isa(S.second.SummaryList.front().get())) + continue; + discoverNodes(ValueInfo(IsAnalysis, &S), FunctionHasParent); + } + + 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; } @@ -748,7 +850,7 @@ 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); @@ -923,6 +1025,56 @@ /// 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 Index: lib/IR/ModuleSummaryIndex.cpp =================================================================== --- lib/IR/ModuleSummaryIndex.cpp +++ 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 @@ 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, Index: lib/LTO/LTO.cpp =================================================================== --- lib/LTO/LTO.cpp +++ lib/LTO/LTO.cpp @@ -50,6 +50,10 @@ #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 @@ ThinLTO.ModuleMap.size()); StringMap> ResolvedODR; + if (DumpThinCGSCCs) + ThinLTO.CombinedIndex.dumpSCCs(outs()); + if (Conf.OptLevel > 0) ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries, ImportLists, ExportLists); Index: lib/Transforms/IPO/FunctionImport.cpp =================================================================== --- lib/Transforms/IPO/FunctionImport.cpp +++ 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" Index: test/ThinLTO/X86/module_summary_graph_traits.ll =================================================================== --- /dev/null +++ test/ThinLTO/X86/module_summary_graph_traits.ll @@ -0,0 +1,58 @@ +; RUN: opt -module-summary %s -o %t1.bc +; RUN: llvm-lto2 run -print-summary-global-ids -dump-thin-cg-sccs %t1.bc -o %t.index.bc \ +; RUN: -r %t1.bc,external,px -r %t1.bc,l2,pl -r %t1.bc,l1,pl \ +; RUN: -r %t1.bc,simple,pl -r %t1.bc,root,pl 2>&1 | FileCheck %s + +; CHECK: 5224464028922159466{{.*}} is external +; CHECK: 765152853862302398{{.*}} is l2 +; CHECK: 17000277804057984823{{.*}} is l1 +; CHECK: 15440740835768581517{{.*}} is simple +; CHECK: 5800840261926955363{{.*}} is root + +; CHECK: SCC (2 nodes) { +; CHECK-NEXT: {{^}} 17000277804057984823 (has loop) +; CHECK-NEXT: {{^}} 765152853862302398 (has loop) +; CHECK-NEXT: } + +; CHECK: SCC (1 node) { +; CHECK-NEXT: {{^}} 15440740835768581517{{$}} +; CHECK-NEXT: } + +; CHECK: SCC (1 node) { +; CHECK-NEXT: External 5224464028922159466{{$}} +; CHECK-NEXT: } + +; CHECK: SCC (1 node) { +; CHECK-NEXT: {{^}} 5800840261926955363{{$}} +; CHECK-NEXT: } + +; Dummy call graph root that points at all roots of the callgraph. +; CHECK: SCC (1 node) { +; CHECK-NEXT: {{^}} 0{{$}} +; CHECK-NEXT: } + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" +target triple = "x86_64-unknown-linux-gnu" + +declare void @external() + +define void @l2() { + call void @l1() + ret void +} + +define void @l1() { + call void @l2() + ret void +} + +define i32 @simple() { + ret i32 23 +} + +define void @root() { + call void @l1() + call i32 @simple() + call void @external() + ret void +}