Remove CallGraphTraits and use equivalent methods in GraphTraits

[eraman]

Summary

D42698 adds child_edge_{begin|end} and children_edges to GraphTraits
which are used here. The reason for this change is to make it easy to
use count propagation on ModulesummaryIndex. As it stands,
CallGraphTraits is in Analysis while ModuleSummaryIndex is in IR.

[davidxl]

lgtm

include/llvm/Analysis/CallGraph.h

template <> struct GraphTraits<CallGraphNode *> {
   static ChildIteratorType child_end(NodeRef N) {
     return ChildIteratorType(N->end(), &CGNGetValue);
   }
 };
 
 template <> struct GraphTraits<const CallGraphNode *> {
   using NodeRef = const CallGraphNode *;
   using CGNPairTy = CallGraphNode::CallRecord;
+  using EdgeRef = const CallGraphNode::CallRecord &;
 
   static NodeRef getEntryNode(const CallGraphNode *CGN) { return CGN; }
   static const CallGraphNode *CGNGetValue(CGNPairTy P) { return P.second; }
 
   using ChildIteratorType =
       mapped_iterator<CallGraphNode::const_iterator, decltype(&CGNGetValue)>;
+  using ChildEdgeIteratorType = CallGraphNode::const_iterator;
 
   static ChildIteratorType child_begin(NodeRef N) {
     return ChildIteratorType(N->begin(), &CGNGetValue);
   }
 
   static ChildIteratorType child_end(NodeRef N) {
     return ChildIteratorType(N->end(), &CGNGetValue);
   }
+
+  static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
+    return N->begin();
+  }
+  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
+
+  static NodeRef edge_dest(EdgeRef E) { return E.second; }
 };
 
 template <>
 struct GraphTraits<CallGraph *> : public GraphTraits<CallGraphNode *> {
   using PairTy =
       std::pair<const Function *const, std::unique_ptr<CallGraphNode>>;
 
   static NodeRef getEntryNode(CallGraph *CGN) {
static nodes_iterator nodes_begin(const CallGraph *CG) {
     return nodes_iterator(CG->begin(), &CGGetValuePtr);
   }
 
   static nodes_iterator nodes_end(const CallGraph *CG) {
     return nodes_iterator(CG->end(), &CGGetValuePtr);
   }
 };
 
-// FIXME: The traits here are not limited to callgraphs and can be moved
-// elsewhere including GraphTraits. They are left here because only algorithms
-// that operate on Callgraphs currently use them. If other algorithms operating
-// on a general graph need edge traversals, these can be moved.
-template <class CallGraphType>
-struct CallGraphTraits : public GraphTraits<CallGraphType> {
-  // Elements to provide:
-
-  // typedef EdgeRef           - Type of Edge token in the graph, which should
-  //                             be cheap to copy.
-  // typedef CallEdgeIteratorType - Type used to iterate over children edges in
-  //                             graph, dereference to a EdgeRef.
-
-  // static CallEdgeIteratorType call_edge_begin(NodeRef)
-  // static CallEdgeIteratorType call_edge_end  (NodeRef)
-  //     Return iterators that point to the beginning and ending of the call
-  //     edges list for the given callgraph node.
-  //
-  // static NodeRef edge_dest(EdgeRef)
-  //     Return the destination node of an edge.
-
-  // If anyone tries to use this class without having an appropriate
-  // specialization, make an error.  If you get this error, it's because you
-  // need to include the appropriate specialization of GraphTraits<> for your
-  // graph, or you need to define it for a new graph type. Either that or
-  // your argument to XXX_begin(...) is unknown or needs to have the proper .h
-  // file #include'd.
-  using CallEdgeIteratorType =
-      typename CallGraphType::UnknownCallGraphTypeError;
-};
-
-template <class GraphType>
-iterator_range<typename CallGraphTraits<GraphType>::CallEdgeIteratorType>
-call_edges(const typename CallGraphTraits<GraphType>::NodeRef &G) {
-  return make_range(CallGraphTraits<GraphType>::call_edge_begin(G),
-                    CallGraphTraits<GraphType>::call_edge_end(G));
-}
-
-template <>
-struct CallGraphTraits<const CallGraph *>
-    : public GraphTraits<const CallGraph *> {
-  using EdgeRef = const CallGraphNode::CallRecord &;
-  using CallEdgeIteratorType = CallGraphNode::const_iterator;
-
-  static CallEdgeIteratorType call_edge_begin(NodeRef N) { return N->begin(); }
-  static CallEdgeIteratorType call_edge_end(NodeRef N) { return N->end(); }
-
-  static NodeRef edge_dest(EdgeRef E) { return E.second; }
-};
-
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_CALLGRAPH_H

include/llvm/Analysis/SyntheticCountsUtils.h

 /// Class with methods to propagate synthetic entry counts.
 ///
 /// This class is templated on the type of the call graph and designed to work
 /// with the traditional per-module callgraph and the summary callgraphs used in
 /// ThinLTO. This contains only static methods and alias templates.
 template <typename CallGraphType> class SyntheticCountsUtils {
 public:
   using Scaled64 = ScaledNumber<uint64_t>;
-  using CGT = CallGraphTraits<CallGraphType>;
+  using CGT = GraphTraits<CallGraphType>;
   using NodeRef = typename CGT::NodeRef;
   using EdgeRef = typename CGT::EdgeRef;
   using SccTy = std::vector<NodeRef>;
 
   using GetRelBBFreqTy = function_ref<Optional<Scaled64>(EdgeRef)>;
   using GetCountTy = function_ref<uint64_t(NodeRef)>;
   using AddCountTy = function_ref<void(NodeRef, uint64_t)>;
 

lib/Analysis/SyntheticCountsUtils.cpp

void SyntheticCountsUtils<CallGraphType>::propagateFromSCC(
   SmallVector<std::pair<NodeRef, EdgeRef>, 8> SCCEdges, NonSCCEdges;
 
   for (auto &Node : SCC)
     SCCNodes.insert(Node);
 
   // Partition the edges coming out of the SCC into those whose destination is
   // in the SCC and the rest.
   for (const auto &Node : SCCNodes) {
-    for (auto &E : call_edges<CallGraphType>(Node)) {
+    for (auto &E : children_edges<CallGraphType>(Node)) {
       if (SCCNodes.count(CGT::edge_dest(E)))
         SCCEdges.emplace_back(Node, E);
       else
         NonSCCEdges.emplace_back(Node, E);
     }
   }
 
   // For nodes in the same SCC, update the counts in two steps:
void SyntheticCountsUtils<CallGraphType>::propagateFromSCC(
   }
 }
 
 /// Propgate synthetic entry counts on a callgraph \p CG.
 ///
 /// This performs a reverse post-order traversal of the callgraph SCC. For each
 /// SCC, it first propagates the entry counts to the nodes within the SCC
 /// through call edges and updates them in one shot. Then the entry counts are
-/// propagated to nodes outside the SCC. This requires \p CallGraphTraits
+/// propagated to nodes outside the SCC. This requires \p GraphTraits
 /// to have a specialization for \p CallGraphType.
 
 template <typename CallGraphType>
 void SyntheticCountsUtils<CallGraphType>::propagate(const CallGraphType &CG,
                                                     GetRelBBFreqTy GetRelBBFreq,
                                                     GetCountTy GetCount,
                                                     AddCountTy AddCount) {
   std::vector<SccTy> SCCs;