1 //===- llvm/ADT/GraphTraits.h - Graph traits template -----------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file defines the little GraphTraits<X> template class that should be 11 /// specialized by classes that want to be iteratable by generic graph 12 /// iterators. 13 /// 14 /// This file also defines the marker class Inverse that is used to iterate over 15 /// graphs in a graph defined, inverse ordering... 16 /// 17 //===----------------------------------------------------------------------===// 18 19 #ifndef LLVM_ADT_GRAPHTRAITS_H 20 #define LLVM_ADT_GRAPHTRAITS_H 21 22 #include "llvm/ADT/STLExtras.h" 23 #include "llvm/ADT/iterator_range.h" 24 25 namespace llvm { 26 27 // GraphTraits - This class should be specialized by different graph types... 28 // which is why the default version is empty. 29 // 30 // This template evolved from supporting `BasicBlock` to also later supporting 31 // more complex types (e.g. CFG and DomTree). 32 // 33 // GraphTraits can be used to create a view over a graph interpreting it 34 // differently without requiring a copy of the original graph. This could 35 // be achieved by carrying more data in NodeRef. See LoopBodyTraits for one 36 // example. 37 template<class GraphType> 38 struct GraphTraits { 39 // Elements to provide: 40 41 // typedef NodeRef - Type of Node token in the graph, which should 42 // be cheap to copy. 43 // typedef ChildIteratorType - Type used to iterate over children in graph, 44 // dereference to a NodeRef. 45 46 // static NodeRef getEntryNode(const GraphType &) 47 // Return the entry node of the graph 48 49 // static ChildIteratorType child_begin(NodeRef) 50 // static ChildIteratorType child_end (NodeRef) 51 // Return iterators that point to the beginning and ending of the child 52 // node list for the specified node. 53 54 // typedef ...iterator nodes_iterator; - dereference to a NodeRef 55 // static nodes_iterator nodes_begin(GraphType *G) 56 // static nodes_iterator nodes_end (GraphType *G) 57 // nodes_iterator/begin/end - Allow iteration over all nodes in the graph 58 59 // typedef EdgeRef - Type of Edge token in the graph, which should 60 // be cheap to copy. 61 // typedef ChildEdgeIteratorType - Type used to iterate over children edges in 62 // graph, dereference to a EdgeRef. 63 64 // static ChildEdgeIteratorType child_edge_begin(NodeRef) 65 // static ChildEdgeIteratorType child_edge_end(NodeRef) 66 // Return iterators that point to the beginning and ending of the 67 // edge list for the given callgraph node. 68 // 69 // static NodeRef edge_dest(EdgeRef) 70 // Return the destination node of an edge. 71 72 // static unsigned size (GraphType *G) 73 // Return total number of nodes in the graph 74 75 // Optionally implement the following: 76 // static unsigned getNumber(NodeRef) 77 // Return a unique number of a node. Numbers are ideally dense, these are 78 // used to store nodes in a vector. 79 // static unsigned getMaxNumber(GraphType *G) 80 // Return the maximum number that getNumber() will return, or 0 if this is 81 // unknown. Intended for reserving large enough buffers. 82 // static unsigned getNumberEpoch(GraphType *G) 83 // Return the "epoch" of the node numbers. Should return a different 84 // number after renumbering, so users can assert that the epoch didn't 85 // change => numbers are still valid. If renumberings are not tracked, it 86 // is always valid to return a constant value. This is solely for to ease 87 // debugging by having a way to detect use of outdated numbers. 88 89 // If anyone tries to use this class without having an appropriate 90 // specialization, make an error. If you get this error, it's because you 91 // need to include the appropriate specialization of GraphTraits<> for your 92 // graph, or you need to define it for a new graph type. Either that or 93 // your argument to XXX_begin(...) is unknown or needs to have the proper .h 94 // file #include'd. 95 using NodeRef = typename GraphType::UnknownGraphTypeError; 96 }; 97 98 namespace detail { 99 template <typename T> 100 using has_number_t = decltype(GraphTraits<T>::getNumber( 101 std::declval<typename GraphTraits<T>::NodeRef>())); 102 } // namespace detail 103 104 /// Indicate whether a GraphTraits<NodeT>::getNumber() is supported. 105 template <typename NodeT> 106 constexpr bool GraphHasNodeNumbers = 107 is_detected<detail::has_number_t, NodeT>::value; 108 109 // Inverse - This class is used as a little marker class to tell the graph 110 // iterator to iterate over the graph in a graph defined "Inverse" ordering. 111 // Not all graphs define an inverse ordering, and if they do, it depends on 112 // the graph exactly what that is. Here's an example of usage with the 113 // df_iterator: 114 // 115 // idf_iterator<Method*> I = idf_begin(M), E = idf_end(M); 116 // for (; I != E; ++I) { ... } 117 // 118 // Which is equivalent to: 119 // df_iterator<Inverse<Method*>> I = idf_begin(M), E = idf_end(M); 120 // for (; I != E; ++I) { ... } 121 // 122 template <class GraphType> 123 struct Inverse { 124 const GraphType &Graph; 125 126 inline Inverse(const GraphType &G) : Graph(G) {} 127 }; 128 129 // Provide a partial specialization of GraphTraits so that the inverse of an 130 // inverse falls back to the original graph. 131 template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {}; 132 133 // Provide iterator ranges for the graph traits nodes and children 134 template <class GraphType> 135 iterator_range<typename GraphTraits<GraphType>::nodes_iterator> 136 nodes(const GraphType &G) { 137 return make_range(GraphTraits<GraphType>::nodes_begin(G), 138 GraphTraits<GraphType>::nodes_end(G)); 139 } 140 template <class GraphType> 141 iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator> 142 inverse_nodes(const GraphType &G) { 143 return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G), 144 GraphTraits<Inverse<GraphType>>::nodes_end(G)); 145 } 146 147 template <class GraphType> 148 iterator_range<typename GraphTraits<GraphType>::ChildIteratorType> 149 children(const typename GraphTraits<GraphType>::NodeRef &G) { 150 return make_range(GraphTraits<GraphType>::child_begin(G), 151 GraphTraits<GraphType>::child_end(G)); 152 } 153 154 template <class GraphType> 155 iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType> 156 inverse_children(const typename GraphTraits<GraphType>::NodeRef &G) { 157 return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G), 158 GraphTraits<Inverse<GraphType>>::child_end(G)); 159 } 160 161 template <class GraphType> 162 iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType> 163 children_edges(const typename GraphTraits<GraphType>::NodeRef &G) { 164 return make_range(GraphTraits<GraphType>::child_edge_begin(G), 165 GraphTraits<GraphType>::child_edge_end(G)); 166 } 167 168 } // end namespace llvm 169 170 #endif // LLVM_ADT_GRAPHTRAITS_H 171