[GraphTraits] Add support for iterating over children edges.

[eraman]

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.

[davidxl]

include/llvm/ADT/GraphTraits.h

56 ↗

(On Diff #132013)

Is there a convention on the naming here? why not call it out_edge_begin|end?

Related, any need for incoming edge iterations?

[davidxl]

looks like the naming follows the node iteration interfaces. lgtm.

llvm/trunk/include/llvm/ADT/GraphTraits.h

struct GraphTraits {
   //    Return iterators that point to the beginning and ending of the child
   //    node list for the specified node.
 
   // typedef  ...iterator nodes_iterator; - dereference to a NodeRef
   // static nodes_iterator nodes_begin(GraphType *G)
   // 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
 
   // 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

 
 template <class GraphType>
 iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType>
 inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) {
   return make_range(GraphTraits<Inverse<GraphType>>::child_begin(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