[GraphTraits] Add support for iterating over children edges.

Summary:
This change is mostly adding comments to GraphTraits describing
interfaces to iterate over children edges of a node. These will
have to be implemented by specializations of GraphTraits. The
non-comment change is the addition of children_edges template
function that returns an iterator range.

The motivation for this is to use it in synthetic count propagation
algorithm and remove the CallGraphTraits class that provide similar
interfaces.

Reviewers: dberlin, davidxl

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D42698

llvm-svn: 323990

1 files changed, 20 insertions, 0 deletions

diff --git a/llvm/include/llvm/ADT/GraphTraits.h b/llvm/include/llvm/ADT/GraphTraits.h
index 225d9eb847f..27c647f4bbb 100644
--- a/llvm/include/llvm/ADT/GraphTraits.h
+++ b/llvm/include/llvm/ADT/GraphTraits.h
@@ -47,6 +47,19 @@ struct GraphTraits {
   // static nodes_iterator nodes_end  (GraphType *G)
   //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 
+  // typedef EdgeRef           - Type of Edge token in the graph, which should
+  //                             be cheap to copy.
+  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
+  //                             graph, dereference to a EdgeRef.
+
+  // static ChildEdgeIteratorType child_edge_begin(NodeRef)
+  // static ChildEdgeIteratorType child_edge_end(NodeRef)
+  //     Return iterators that point to the beginning and ending of the
+  //     edge list for the given callgraph node.
+  //
+  // static NodeRef edge_dest(EdgeRef)
+  //     Return the destination node of an edge.
+
   // static unsigned       size       (GraphType *G)
   //    Return total number of nodes in the graph
 
@@ -111,6 +124,13 @@ inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
                     GraphTraits<Inverse<GraphType>>::child_end(G));
 }
 
+template <class GraphType>
+iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType>
+children_edges(const typename GraphTraits<GraphType>::NodeRef &G) {
+  return make_range(GraphTraits<GraphType>::child_edge_begin(G),
+                    GraphTraits<GraphType>::child_edge_end(G));
+}
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_GRAPHTRAITS_H