LLVM  16.0.0git
GraphTraits.h
Go to the documentation of this file.
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 
23 
24 namespace llvm {
25 
26 // GraphTraits - This class should be specialized by different graph types...
27 // which is why the default version is empty.
28 //
29 // This template evolved from supporting `BasicBlock` to also later supporting
30 // more complex types (e.g. CFG and DomTree).
31 //
32 // GraphTraits can be used to create a view over a graph interpreting it
33 // differently without requiring a copy of the original graph. This could
34 // be achieved by carrying more data in NodeRef. See LoopBodyTraits for one
35 // example.
36 template<class GraphType>
37 struct GraphTraits {
38  // Elements to provide:
39 
40  // typedef NodeRef - Type of Node token in the graph, which should
41  // be cheap to copy.
42  // typedef ChildIteratorType - Type used to iterate over children in graph,
43  // dereference to a NodeRef.
44 
45  // static NodeRef getEntryNode(const GraphType &)
46  // Return the entry node of the graph
47 
48  // static ChildIteratorType child_begin(NodeRef)
49  // static ChildIteratorType child_end (NodeRef)
50  // Return iterators that point to the beginning and ending of the child
51  // node list for the specified node.
52 
53  // typedef ...iterator nodes_iterator; - dereference to a NodeRef
54  // static nodes_iterator nodes_begin(GraphType *G)
55  // static nodes_iterator nodes_end (GraphType *G)
56  // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
57 
58  // typedef EdgeRef - Type of Edge token in the graph, which should
59  // be cheap to copy.
60  // typedef ChildEdgeIteratorType - Type used to iterate over children edges in
61  // graph, dereference to a EdgeRef.
62 
63  // static ChildEdgeIteratorType child_edge_begin(NodeRef)
64  // static ChildEdgeIteratorType child_edge_end(NodeRef)
65  // Return iterators that point to the beginning and ending of the
66  // edge list for the given callgraph node.
67  //
68  // static NodeRef edge_dest(EdgeRef)
69  // Return the destination node of an edge.
70 
71  // static unsigned size (GraphType *G)
72  // Return total number of nodes in the graph
73 
74  // If anyone tries to use this class without having an appropriate
75  // specialization, make an error. If you get this error, it's because you
76  // need to include the appropriate specialization of GraphTraits<> for your
77  // graph, or you need to define it for a new graph type. Either that or
78  // your argument to XXX_begin(...) is unknown or needs to have the proper .h
79  // file #include'd.
80  using NodeRef = typename GraphType::UnknownGraphTypeError;
81 };
82 
83 // Inverse - This class is used as a little marker class to tell the graph
84 // iterator to iterate over the graph in a graph defined "Inverse" ordering.
85 // Not all graphs define an inverse ordering, and if they do, it depends on
86 // the graph exactly what that is. Here's an example of usage with the
87 // df_iterator:
88 //
89 // idf_iterator<Method*> I = idf_begin(M), E = idf_end(M);
90 // for (; I != E; ++I) { ... }
91 //
92 // Which is equivalent to:
93 // df_iterator<Inverse<Method*>> I = idf_begin(M), E = idf_end(M);
94 // for (; I != E; ++I) { ... }
95 //
96 template <class GraphType>
97 struct Inverse {
98  const GraphType &Graph;
99 
100  inline Inverse(const GraphType &G) : Graph(G) {}
101 };
102 
103 // Provide a partial specialization of GraphTraits so that the inverse of an
104 // inverse falls back to the original graph.
105 template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {};
106 
107 // Provide iterator ranges for the graph traits nodes and children
108 template <class GraphType>
110 nodes(const GraphType &G) {
113 }
114 template <class GraphType>
115 iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator>
116 inverse_nodes(const GraphType &G) {
117  return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G),
118  GraphTraits<Inverse<GraphType>>::nodes_end(G));
119 }
120 
121 template <class GraphType>
122 iterator_range<typename GraphTraits<GraphType>::ChildIteratorType>
126 }
127 
128 template <class GraphType>
129 iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType>
131  return make_range(GraphTraits<Inverse<GraphType>>::child_begin(G),
132  GraphTraits<Inverse<GraphType>>::child_end(G));
133 }
134 
135 template <class GraphType>
136 iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType>
140 }
141 
142 } // end namespace llvm
143 
144 #endif // LLVM_ADT_GRAPHTRAITS_H
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::Inverse::Graph
const GraphType & Graph
Definition: GraphTraits.h:98
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::inverse_children
iterator_range< typename GraphTraits< Inverse< GraphType > >::ChildIteratorType > inverse_children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:130
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::Inverse::Inverse
Inverse(const GraphType &G)
Definition: GraphTraits.h:100
llvm::nodes
iterator_range< typename GraphTraits< GraphType >::nodes_iterator > nodes(const GraphType &G)
Definition: GraphTraits.h:110
llvm::children
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:123
iterator_range.h
llvm::children_edges
iterator_range< typename GraphTraits< GraphType >::ChildEdgeIteratorType > children_edges(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:137
llvm::inverse_nodes
iterator_range< typename GraphTraits< Inverse< GraphType > >::nodes_iterator > inverse_nodes(const GraphType &G)
Definition: GraphTraits.h:116
llvm::Inverse
Definition: GraphTraits.h:97
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::GraphTraits< FlatIt< RegionNode * > >::NodeRef
typename FlatIt< RegionNode * > ::UnknownGraphTypeError NodeRef
Definition: GraphTraits.h:80
llvm::GraphTraits
Definition: GraphTraits.h:37