[ThinLTO] Add GraphTraits for FunctionSummaries

[ncharlie]

Summary

Depends on D36233

Add GraphTraits definitions to the FunctionSummary and ModuleSummaryIndex classes. These GraphTraits will be used to construct find SCC's in ThinLTO analysis passes.

[ncharlie]

Diff against D36233 rather than master.

[ncharlie]

Since this patch depends on D36233, I'm diffing against it to show minimal changes.

include/llvm/IR/ModuleSummaryIndex.h

405

There are some external functions (i.e. libc functions) that aren't included in the summary, so I create an empty functionsummary for them.

909

Should the first callee be the entry node or the caller function itself?

[ncharlie]

Make the entry node the function itself.

[ncharlie]

How should I test this and ensure it's working properly?

[ncharlie]

simplify code by using mapped_iterator rather than custom implementation.

[ncharlie]

Added GraphTraits for ModuleSummaryIndex

include/llvm/IR/ModuleSummaryIndex.h

945

This entry node isn't necessarily at the bottom of the callgraph. I'm not sure how to address this problem at the moment.

[ncharlie]

include/llvm/IR/ModuleSummaryIndex.h

912

This is causing problems. The scc_iterator gets stuck on these functionsummaries since they're not in the original graph, which causes it to terminate before going through all the SCCs in the summary callgraph.

[ncharlie]

include/llvm/IR/ModuleSummaryIndex.h

949

Looking more closely at the scc_iterator code, I don't think I need to describe nodes_begin/nodes_end. If that's the case I'll remove them (I'd like to get rid of my fsummary_iterator implementation if possible)

[ncharlie]

removed fsummary_iterator since it's not needed for the scc_iterator

[ncharlie]

For some reason, the scc_iterator isn't visiting the whole graph, and only visits the children of the entryNode. How should I move across all SCCs in the Index?

[ncharlie]

Ah, I think I realized what the entryNode should be: I should topologically sort the nodes in the ModuleSummaryIndex and take the first FunctionSummary. Right now the entry node is arbitrary.

[ncharlie]

I don't think I can use a topological sort in this case since the FunctionSummary callgraph isn't necessarily a DAG, so if there's a cycle it would make the sort useless.

Instead, I tried using the main function as the entry node and that worked. Any suggestions on a clean way of implementing this rather than hard coding a lookup for "main" in the Index?

[davide]

In D36311#842488, @ncharlie wrote:

I don't think I can use a topological sort in this case since the FunctionSummary callgraph isn't necessarily a DAG, so if there's a cycle it would make the sort useless.

No callgraph is guaranteed to be a DAG, what's a DAG is the condensed graph, where you contract every node of a component to a single vertex.
The data-flow algorithms generally work first propagating within a single SCC (using a worklist algorithm) until you hit a maximal fixpoint, then propagating topologically the facts you learned across the graphs of SCCs.

Instead, I tried using the main function as the entry node and that worked. Any suggestions on a clean way of implementing this rather than hard coding a lookup for "main" in the Index?

I'm not sure you're always guaranteed to have the main function as entry point of your program.

[ncharlie]

In D36311#843066, @davide wrote:

I'm not sure you're always guaranteed to have the main function as entry point of your program.

Right - how would you recommend finding the root node of the callgraph so I can return that in the getEntryNode for the GraphTraits for the ModuleSummaryIndex? Since right now, it's just arbitrarily finding a FunctionSummary in the Index.

[ncharlie]

I tried implementing a search to find the root nodes in the Index callgraph. But there can be multiple root nodes in the callgraph and we can only return one node from GraphTraits<ModuleSummaryIndex *>::getEntry. Since I didn't know how to pick the correct root, I didn't go with that solution. Is there any information I can find in the Index that indicates the entry point?

[tejohnson]

In D36311#843271, @ncharlie wrote:

I tried implementing a search to find the root nodes in the Index callgraph. But there can be multiple root nodes in the callgraph and we can only return one node from GraphTraits<ModuleSummaryIndex *>::getEntry. Since I didn't know how to pick the correct root, I didn't go with that solution. Is there any information I can find in the Index that indicates the entry point?

Looking at how the GraphTraits is implemented for the CFG, it returns a special "ExternalCallingNode", that is created to contain edges to all functions that may be called externally (e.g. external linkage or address taken). See CallGraph::addToCallGraph() in CallGraph.cpp. Perhaps you can create such a dummy node in the index, which has edges to all the root nodes, and return that as the entry node?

[ncharlie]

In D36311#843273, @tejohnson wrote:

Perhaps you can create such a dummy node in the index, which has edges to all the root nodes, and return that as the entry node?

Yeah, I think that'll work! I've been staring at the CallGraph::addToCallGraph() for the last few days but didn't think to apply the same idea of a dummy root node to the Index :P

Thanks!

[tejohnson]

In D36311#834662, @ncharlie wrote:

How should I test this and ensure it's working properly?

Maybe add an scc dumper facility for the module summary graph, which creates an scc_iterator from the module summary and just dumps the nodes in each scc, that can be checked using a Lit based test

include/llvm/IR/ModuleSummaryIndex.h

28

Not needed in this patch?

912

In what way does it get stuck? The CallGraph.h has a dedicated CallsExternalNode for calls to external functions, but it seems like you are doing something similar here with a static ExternalFunction.

[ncharlie]

Maybe add an scc dumper facility for the module summary graph, which creates an scc_iterator from the module summary and just dumps the nodes in each scc, that can be checked using a Lit based test

I'll look into adding this.

include/llvm/IR/ModuleSummaryIndex.h

28

Oops - leftover from a different branch. I'll remove that.

912

Sorry, nvm that comment - I was misattributing it to external nodes before, but it was really just because my entry point for the Index was wrong.

[ncharlie]

Create dummy root for index callgraph entry point.

[tejohnson]

include/llvm/IR/ModuleSummaryIndex.h

479

This isn't the first callee, it is the function summary whose callees we will walk as children.

605

doxygen comment needed

643

Since you set FunctionHasParent on the line above, I think this would always already return true for isDiscovered.

659

Better to reverse sense of condition and do continue.

660

Why are you using original name here? I guess it is because you don't have easy access to the normal GUID? Can you fix this by changing FunctionHasParent to key off the ValueInfo instead of the FunctionSummary? I.e. then in the above loop over the index you would call discoverNodes with ValueInfo(&S). Then here you have direct access to the ValueInfo.

I guess the type of NodeRef and return type of fsumFromEdge need to change to ValueInfo correspondingly.

668

Add a comment describing the parameters you are passing constant values. E.g. "/*NotEligibleToImport=*/true".

[ncharlie]

Updated according to comments
Added test.

[davide]

include/llvm/IR/ModuleSummaryIndex.h

110

Add a message.

465–473

This is not really readable. I wonder if you can make it shorter.

636

dyn_cast<> + assert != nullptr ?

lib/IR/ModuleSummaryIndex.cpp

78

Shouldn't this be under NDEBUG || LLVM_ENABLE_DUMP (or whatever it's called?)

[tejohnson]

Getting there, thanks!

include/llvm/IR/ModuleSummaryIndex.h

465–473

Not sure how to make the constructor invocation shorter, but perhaps the code that invokes make_unique could be extracted out to a helper and invoked both here and below where the dummy call graph root node is being constructed. It only needs to take a vector of edges since that is the only difference AFAICT between the 2 invocations.

639

Simplify the above by simply doing:

if (FunctionHasParent.find(C.first) != FunctionHasParent.end())

continue;

Actually - I don't think this is quite correct. We would have emplaced an entry for a function (with bool of false) if we encountered it first through the index walk in the loop below this. So I think you are going to need to assign the result of find() to a variable and then continue if it is != end() and is set to true.

Not sure if this fix is testable - I suppose you were ending up with more nodes than necessary connected to the CallGraphRoot, but I'm not sure offhand what the implication of that is.

647

Needs comment (I can't remember offhand why we would have an index entry with an empty SummaryList - oh, declarations right? I don't think those will show up in the combined index but still ok here but needs to be documented).

tools/llvm-lto2/llvm-lto2.cpp

396 ↗

(On Diff #112344)

I'm not sure llvm-lto2 is the right place for this. Specifically because we normally want to dump these on the combined index that is usually in-memory. Maybe add an option to LTO.cpp and optionally dump it out at the start of runThinLTO?

(Note also this appears to be built on top of your llvm-lto2 with the dump-summary change, which unfortunately we have not gotten agreement to commit yet)

[ncharlie]

include/llvm/IR/ModuleSummaryIndex.h

465–473

Yeah - having a createDummyNode function (or something like that) would definitely help with the readability.

lib/IR/ModuleSummaryIndex.cpp

78

Won't that remove it in non-debug builds though? That would break the new llvm-lto2 dump-sccs subcommand. That's fine if llvm-lto2 isn't expected to be used except in debug builds.

tools/llvm-lto2/llvm-lto2.cpp

396 ↗

(On Diff #112344)

Maybe add an option to LTO.cpp and optionally dump it out at the start of runThinLTO?

Yeah, I though it was a bit weird having it in here. I'll replace it with a hidden flag in LTO.cpp.

[ncharlie]

test/ThinLTO/X86/module_summary_graph_traits.ll

33

Despite the indirect recursion in l1/l2, the SCCs only have 1 node in each. The loop is still detected (with the scc_iterator::hasLoop function), but there's an SCC for each function.

[tejohnson]

This looks really good, just a few minor comments. But I do have a concern about the test and it not showing the multiple node SCCs that I would expect. Can you investigate?

include/llvm/IR/ModuleSummaryIndex.h

330

document

624

Notice this is no longer lazily calculated. Was there a specific reason for the change? I suppose one reason not to do that is that you'd want any changes to the Index reflected in this in between subsequent SCC graph constructions (which should not happen frequently anyway).

639

comment

647

nit - move comment to preceding line.

test/ThinLTO/X86/module_summary_graph_traits.ll

7

Put a comment above each of these as to which function name it corresponds to.

33

Hmm, that seems wrong? Wouldn't we incorrectly think these were NoRecurse then? Wondering also why there are 3 functions marked as "has loop". I assume that is root() - but we haven't done any inlining that would cause this right?

[ncharlie]

include/llvm/IR/ModuleSummaryIndex.h

624

I was having trouble with the ownership of the unique_ptr node generated by this function, so I decided it was simpler to just pass the FunctionSummary directly rather than allocating and managing the memory for it.

test/ThinLTO/X86/module_summary_graph_traits.ll

33

I'll look into this.

[ncharlie]

Added operator!= and operator<

[ncharlie]

Any updates on this @tejohnson @davide ?

[tejohnson]

In D36311#896969, @ncharlie wrote:

Any updates on this @tejohnson @davide ?

Sorry - didn't realize this was ready for re-review! I had a question about the tests earlier (see below). The comment wasn't marked as done. Although I see now that the test has changed a bit - did you resolve this? I will take a look this morning.

test/ThinLTO/X86/module_summary_graph_traits.ll

33

Did you figure this out?

[ncharlie]

In D36311#896973, @tejohnson wrote:

In D36311#896969, @ncharlie wrote:

Any updates on this @tejohnson @davide ?

Sorry - didn't realize this was ready for re-review! I had a question about the tests earlier (see below). The comment wasn't marked as done. Although I see now that the test has changed a bit - did you resolve this? I will take a look this morning.

Ah sorry - forgot to mark it. Yeah - it's corrected now. Updated the tests accordingly.

[tejohnson]

Just minor comments left at this point, I noted a few places where you hadn't yet addressed my previous commenting nits, plus a question about paring down the new operators, and some suggestions for minorly beefing up the matching you are doing on the test lines.

include/llvm/IR/ModuleSummaryIndex.h

119

I see you have both const and non-const parameter versions of operator== and operator<, but only the non-const parameter version of operator!=. Why is that? Also, since ValueInfo::getGUID is const, I would think you should be able to have only a single version of each operator overload, all taking const ValueInfo.

330

Not done yet.

639

Not done yet

647

Not done yet

test/ThinLTO/X86/module_summary_graph_traits.ll

7

Please add this - I think what you are getting now makes sense, but it would be really helpful to have these documented. BTW, you can check this correlation by passing -print-summary-global-ids to llvm-lto2.

13

Add "{{$}}" after each of these that shouldn't be followed by " (has loop)".
Ditto for matching start of line for those that shouldn't be preceeded by "External". I.e. I think preceeding the GUID you are matching with "{{^}} " should do it (match start of line followed by one space which appears to be how these are getting emitted).

25

What is this node? Ah, the dummy call graph root? Document.

[ncharlie]

include/llvm/IR/ModuleSummaryIndex.h

119

OK - it works without the non-const operators, so I removed them.

[ncharlie]

Any updates on this?

[tejohnson]

Sorry, I missed these being updated. Will take another pass through but it looks like you have addressed my comments.

Easwaran - can this be used to do the call graph walks you need for synthetic counts propagation? If not we need to figure out why, because I see you are going in a different direction in D42311.

[tejohnson]

LGTM with a few suggestions below that don't require a re-review. Minor update needed to the ValueInfo comparisons due to a recent patch (see the comment I left there), and a few efficiency improvements. Go ahead and submit once those are fixed and tests pass and you've uploaded the new patch here for posterity.

include/llvm/IR/ModuleSummaryIndex.h

109

The asserts in these comparison operators will need a slight update after the changes to ValueInfo in r323062. I think you can just change Ref to getRef() on the given ValueInfo objects.

625

Add a comment above this documenting what the bool represents.

631

Presumably more efficient to check if there is already a map entry and return early if so (we'll eventually skip all the callees below since they would already have been visited, but might as well not even do that processing). Also, no need for make_pair when using emplace. I.e. change this to:

auto S = FunctionHasParent.emplace(V, false);
// Stop if we have already discovered this node.
if (!S.second)

return;

643

We can actually skip the discoverNodes if it was in the map (even if S->second was false), since we would already have walked it's callees if it was added to the map when encountered in the for loop below over the index. Additionally, no need to do another map lookup to set the value to true, since you already have the entry via the iterator, although even better to just do via emplace. So you should be able to change this block to:

Insert the node if necessary
auto S = FunctionHasParent.emplace(C.first, true);
Skip nodes that already had parents
if (!S.second && S.first->second)

continue;

// If we just inserted this node, discover it, otherwise just note that it now has a parent.
if (S.second)

discoverNodes(C.first);

else

S.first->second = true;

I think this should work...

652

getValueInfo will lookup the given GUID in the GlobalValueMap - the same map we are iterating over in this loop. Can't we just do "discoverNodes(S.second)"?

[eraman]

include/llvm/IR/ModuleSummaryIndex.h

111

The current version of this file has a isSpecialKey(ValueInfo) in DenseMapInfo that compares a ValueInfo with tombstone and empty keys. This breaks with the == overload since the tombstone and empty keys don't have valid pointers and this tries dereferencing them. A fix is to not use == in isSpecialKey but call getRef and compare the pointers.

[ncharlie]

Merged master, fixed tests, minor tweaks.

[ncharlie]

include/llvm/IR/ModuleSummaryIndex.h

858

@tejohnson

I just wanted to double check that this functionality for getting a FunctionSummary from a ValueInfo is sane. It expects the first value in the SummaryList to be either a FunctionSummary (in which case it returns it) or an AliasSummary (in which case it gets its aliasee, expecting a FunctionSummary).

[tejohnson]

It looks like D36850 got accidentally merged into this version of the patch -make sure to remove that.

include/llvm/IR/ModuleSummaryIndex.h

625

s/Functinos/Functions
s/mark/marked/

858

You can just invoke GlobalValueSummary::getBaseObject which will return the aliasee if it is an alias, otherwise the this pointer. It looks like you should just assert then that the resulting object is a FunctionSummary, since the caller expects it to be one (and looks like this is just called when walking call edges, so should always be the case).

[eraman]

include/llvm/IR/ModuleSummaryIndex.h

880

From the comments in GraphTraits, NodeRef is "Type of Node token in the graph, which should be cheap to copy." ValueInfo is cheap to copy now, but if something later gets added to it it might not be cheap to copy anymore. It is preferable to keep NodeRef as a reference (or pointer) to ValueInfo. Also, you could use using instead of typedef.

[tejohnson]

In D36311#990888, @tejohnson wrote:

It looks like D36850 got accidentally merged into this version of the patch -make sure to remove that.

Hi Charles,

I was just chatting with Easwaran - he's using your patch and building on top of it for frequency propagation changes. Would you be able to address my last round of comments which are all minor and don't need a re-review, and commit this soon (say in the next week)? If not, let me know if you would like one of us to commit it (attributing it to you). (Easwaran says don't worry about his comment regarding the NodeRef for this patch.)

Thanks!
Teresa

[ncharlie]

fixed borked diff

[ncharlie]

Committed in rL324854

[tejohnson]

Thanks! Looks like the test accidentally got left out of the commit, so please commit that as a follow-on.

[ncharlie]

In D36311#1004646, @tejohnson wrote:

Thanks! Looks like the test accidentally got left out of the commit, so please commit that as a follow-on.

Ah, good catch - thanks. Committed the test as well.

[ncharlie]

Use function_ref rather std::function, becuase of bug in clang.

[ncharlie]

Committed patch to use function_ref rather than std::function.

[ncharlie]

Move lambda into static function.

include/llvm/IR/ModuleSummaryIndex.h

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/Module.h"
 #include <algorithm>
 #include <array>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <map>
 #include <memory>
 #include <set>
 #include <string>
 #include <utility>
 #include <vector>
-#include <llvm/Support/raw_ostream.h>
 
 namespace llvm {
 
 namespace yaml {
 
 template <typename T> struct MappingTraits;
 
 } // end namespace yaml
struct ValueInfo {
   GlobalValue::GUID getGUID() const { return Ref->first; }
   const GlobalValue *getValue() const { return Ref->second.GV; }
 
   ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const {
     return Ref->second.SummaryList;
   }
 };
 
-static bool operator==(ValueInfo A, ValueInfo B) {
-  assert(A.Ref && B.Ref);
+inline bool operator==(const ValueInfo &A, const ValueInfo &B) {
+  assert(A.Ref && B.Ref && "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");
+  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");
   return A.getGUID() < B.getGUID();
 }
 
 template <> struct DenseMapInfo<ValueInfo> {
   static inline ValueInfo getEmptyKey() {
     return ValueInfo((GlobalValueSummaryMapTy::value_type *)-1);
   }
return FunctionSummary(
         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.
   unsigned InstCount;
 
   /// Function attribute flags. Used to track if a function accesses memory,
public:
 
   /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
   ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
 
   /// Returns the list of type identifiers used by this function in
   /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
   /// represented as GUIDs.
   ArrayRef<GlobalValue::GUID> type_tests() const {
     if (TIdInfo)
       return TIdInfo->TypeTests;
     return {};
   }
 
   /// Returns the list of virtual calls made by this function using
   /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
   /// integer arguments.
   ArrayRef<VFuncId> type_test_assume_vcalls() const {
public:
 
   /// Add a type test to the summary. This is used by WholeProgramDevirt if we
   /// were unable to devirtualize a checked call.
   void addTypeTest(GlobalValue::GUID Guid) {
     if (!TIdInfo)
       TIdInfo = llvm::make_unique<TypeIdInfo>();
     TIdInfo->TypeTests.push_back(Guid);
   }
+
+  friend struct GraphTraits<ValueInfo>;
 };
 
 template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
   static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
 
   static FunctionSummary::VFuncId getTombstoneKey() {
     return {0, uint64_t(-2)};
   }
 
   static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R) {
     return L.GUID == R.GUID && L.Offset == R.Offset;
   }
 
   static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
 };
 
 template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
   static FunctionSummary::ConstVCall getEmptyKey() {
     return {{0, uint64_t(-1)}, {}};
   }
 
   static FunctionSummary::ConstVCall getTombstoneKey() {
     return {{0, uint64_t(-2)}, {}};
   }
 
   static bool isEqual(FunctionSummary::ConstVCall L,
                       FunctionSummary::ConstVCall R) {
     return DenseMapInfo<FunctionSummary::VFuncId>::isEqual(L.VFunc, R.VFunc) &&
            L.Args == R.Args;
   }
 
   static unsigned getHashValue(FunctionSummary::ConstVCall I) {
     return I.VFunc.GUID;
   }
private:
   /// GUIDs, it will be mapped to 0.
   std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
 
   /// Indicates that summary-based GlobalValue GC has run, and values with
   /// GVFlags::Live==false are really dead. Otherwise, all values must be
   /// considered live.
   bool WithGlobalValueDeadStripping = false;
 
   std::set<std::string> CfiFunctionDefs;
   std::set<std::string> CfiFunctionDecls;
 
   // YAML I/O support.
   friend yaml::MappingTraits<ModuleSummaryIndex>;
 
   GlobalValueSummaryMapTy::value_type *
   getOrInsertValuePtr(GlobalValue::GUID GUID) {
     return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo{}).first;
   }
 
 public:
   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(); }
 
   // Calculate the callgraph root
   FunctionSummary calculateCallGraphRoot() {
     std::map<ValueInfo, bool> FunctionHasParent;
     std::function<void(ValueInfo)> 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));
 
       FunctionSummary *F =
           dyn_cast<FunctionSummary>(V.getSummaryList().front().get());
       assert(F != nullptr && "Expected FunctionSummary node");
 
       for (auto &C : F->calls()) {
         auto S = FunctionHasParent.find(C.first);
+        // Skip nodes that we're sure have parents
         if (S != FunctionHasParent.end() && S->second)
           continue;
         FunctionHasParent[C.first] = true;
         discoverNodes(C.first);
       }
     };
 
     for (auto &S : *this) {
       // Skip external functions
       if (!S.second.SummaryList.size() ||
           !isa<FunctionSummary>(S.second.SummaryList.front().get()))
         continue;
       discoverNodes(getValueInfo(S.first));
     }
 
     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{}));
     }
     assert(Edges.size() && "Couldn't find any roots in index callgraph!");
     auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
     return CallGraphRoot;
   }
 
   bool withGlobalValueDeadStripping() const {
     return WithGlobalValueDeadStripping;
   }
   void setWithGlobalValueDeadStripping() {
     WithGlobalValueDeadStripping = true;
   }
 
   bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
     return !WithGlobalValueDeadStripping || GVS->isLive();
   }
public:
   /// (GUID -> Summary).
   void collectDefinedFunctionsForModule(StringRef ModulePath,
                                         GVSummaryMapTy &GVSummaryMap) const;
 
   /// Collect for each module the list of Summaries it defines (GUID ->
   /// Summary).
   void collectDefinedGVSummariesPerModule(
       StringMap<GVSummaryMapTy> &ModuleToDefinedGVSummaries) const;
+
+  void dumpSCCs(raw_ostream &O);
+};
+
+/// 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().get());
+    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().get());
+    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;
+    G.SummaryList.push_back(std::move(Root));
+    static auto P =
+        GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G));
+    return ValueInfo(&P);
+  }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_IR_MODULESUMMARYINDEX_H

lib/IR/ModuleSummaryIndex.cpp

 //===-- ModuleSummaryIndex.cpp - Module Summary Index ---------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the module index and summary classes for the
 // IR library.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/ModuleSummaryIndex.h"
+#include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/StringMap.h"
+#include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
+FunctionSummary FunctionSummary::ExternalNode =
+    FunctionSummary::makeDummyFunctionSummary({});
+
 // Collect for the given module the list of function it defines
 // (GUID -> Summary).
 void ModuleSummaryIndex::collectDefinedFunctionsForModule(
     StringRef ModulePath, GVSummaryMapTy &GVSummaryMap) const {
   for (auto &GlobalList : *this) {
     auto GUID = GlobalList.first;
     for (auto &GlobSummary : GlobalList.second.SummaryList) {
       auto *Summary = dyn_cast_or_null<FunctionSummary>(GlobSummary.get());
bool ModuleSummaryIndex::isGUIDLive(GlobalValue::GUID GUID) const {
   const auto &SummaryList = VI.getSummaryList();
   if (SummaryList.empty())
     return true;
   for (auto &I : SummaryList)
     if (isGlobalValueLive(I.get()))
       return true;
   return false;
 }
+
+LLVM_DUMP_METHOD
+void ModuleSummaryIndex::dumpSCCs(raw_ostream &O) {
+  for (scc_iterator<ModuleSummaryIndex *> I =
+           scc_begin<ModuleSummaryIndex *>(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<FunctionSummary>(V.getSummaryList().front().get());
+      O << " " << (F == nullptr ? "External" : "") << " " << utostr(V.getGUID())
+        << (I.hasLoop() ? " (has loop)" : "") << "\n";
+    }
+    O << "}\n";
+  }
+}

lib/LTO/LTO.cpp

 #include <set>
 
 using namespace llvm;
 using namespace lto;
 using namespace object;
 
 #define DEBUG_TYPE "lto"
 
+static cl::opt<bool>
+    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,
     TinyPtrVector<const std::pair<const std::string, TypeIdSummary> *>>
     TypeIdSummariesByGuidTy;
 
 // Returns a unique hash for the Module considering the current list of
 // export/import and other global analysis results.
if (!ModuleToDefinedGVSummaries.count(Mod.first))
       ModuleToDefinedGVSummaries.try_emplace(Mod.first);
 
   StringMap<FunctionImporter::ImportMapTy> ImportLists(
       ThinLTO.ModuleMap.size());
   StringMap<FunctionImporter::ExportSetTy> ExportLists(
       ThinLTO.ModuleMap.size());
   StringMap<std::map<GlobalValue::GUID, GlobalValue::LinkageTypes>> ResolvedODR;
 
+  if (DumpThinCGSCCs)
+    ThinLTO.CombinedIndex.dumpSCCs(outs());
+
   if (Conf.OptLevel > 0) {
     ComputeCrossModuleImport(ThinLTO.CombinedIndex, ModuleToDefinedGVSummaries,
                              ImportLists, ExportLists);
 
     std::set<GlobalValue::GUID> ExportedGUIDs;
     for (auto &Res : GlobalResolutions) {
       // First check if the symbol was flagged as having external references.
       if (Res.second.Partition != GlobalResolution::External)

test/ThinLTO/X86/module_summary_graph_traits.ll

+; 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: {{^}} 765152853862302398 (has loop)
+; CHECK-NEXT: {{^}} 17000277804057984823 (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
+}