Index: include/llvm/IR/ModuleSummaryIndex.h =================================================================== --- include/llvm/IR/ModuleSummaryIndex.h +++ include/llvm/IR/ModuleSummaryIndex.h @@ -37,7 +37,6 @@ #include #include #include -#include namespace llvm { @@ -163,14 +162,21 @@ bool isDSOLocal() const; }; -static bool operator==(ValueInfo A, ValueInfo B) { - assert(A.Ref && B.Ref); - 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.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.Ref && B.Ref && "Need ValueInfo with non-null Ref to compare GUIDs"); + assert(A.getRef() && B.getRef() && + "Need ValueInfo with non-null Ref to compare GUIDs"); return A.getGUID() < B.getGUID(); } @@ -416,7 +422,7 @@ return FunctionSummary( FunctionSummary::GVFlags( GlobalValue::LinkageTypes::AvailableExternallyLinkage, - /*NotEligibleToImport=*/true, /*Live=*/true), + /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false), 0, FunctionSummary::FFlags{}, std::vector(), std::move(Edges), std::vector(), std::vector(), @@ -547,6 +553,8 @@ TIdInfo = llvm::make_unique(); TIdInfo->TypeTests.push_back(Guid); } + + friend struct GraphTraits; }; template <> struct DenseMapInfo { @@ -745,24 +753,37 @@ // 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 - FunctionHasParent.emplace(std::make_pair(V, false)); + 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()) { - auto S = FunctionHasParent.find(C.first); - if (S != FunctionHasParent.end() && S->second) + // 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; - FunctionHasParent[C.first] = true; - discoverNodes(C.first); + + if (S.second) + discoverNodes(C.first); + else + S.first->second = true; } }; @@ -771,7 +792,7 @@ if (!S.second.SummaryList.size() || !isa(S.second.SummaryList.front().get())) continue; - discoverNodes(getValueInfo(S.first)); + discoverNodes(ValueInfo(IsAnalysis, &S)); } std::vector Edges; @@ -781,7 +802,10 @@ continue; // skip over non-root nodes Edges.push_back(std::make_pair(P.first, CalleeInfo{})); } - assert(Edges.size() && "Couldn't find any roots in index callgraph!"); + if (Edges.empty()) { + // Failed to find root - return an empty node + return FunctionSummary::makeDummyFunctionSummary({}); + } auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges); return CallGraphRoot; } @@ -809,7 +833,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); @@ -984,6 +1008,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 +}