1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
| //===- llvm/ADT/GraphTraits.h - Graph traits template -----------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the little GraphTraits<X> template class that should be
// specialized by classes that want to be iteratable by generic graph iterators.
//
// This file also defines the marker class Inverse that is used to iterate over
// graphs in a graph defined, inverse ordering...
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_GRAPHTRAITS_H
#define LLVM_ADT_GRAPHTRAITS_H
#include "llvm/ADT/iterator_range.h"
namespace llvm {
// GraphTraits - This class should be specialized by different graph types...
// which is why the default version is empty.
//
// This template evolved from supporting `BasicBlock` to also later supporting
// more complex types (e.g. CFG and DomTree).
//
// GraphTraits can be used to create a view over a graph interpreting it
// differently without requiring a copy of the original graph. This could
// be achieved by carrying more data in NodeRef. See LoopBodyTraits for one
// example.
template<class GraphType>
struct GraphTraits {
// Elements to provide:
// typedef NodeRef - Type of Node token in the graph, which should
// be cheap to copy.
// typedef ChildIteratorType - Type used to iterate over children in graph,
// dereference to a NodeRef.
// static NodeRef getEntryNode(const GraphType &)
// Return the entry node of the graph
// static ChildIteratorType child_begin(NodeRef)
// static ChildIteratorType child_end (NodeRef)
// 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
// file #include'd.
using NodeRef = typename GraphType::UnknownGraphTypeError;
};
// Inverse - This class is used as a little marker class to tell the graph
// iterator to iterate over the graph in a graph defined "Inverse" ordering.
// Not all graphs define an inverse ordering, and if they do, it depends on
// the graph exactly what that is. Here's an example of usage with the
// df_iterator:
//
// idf_iterator<Method*> I = idf_begin(M), E = idf_end(M);
// for (; I != E; ++I) { ... }
//
// Which is equivalent to:
// df_iterator<Inverse<Method*>> I = idf_begin(M), E = idf_end(M);
// for (; I != E; ++I) { ... }
//
template <class GraphType>
struct Inverse {
const GraphType &Graph;
inline Inverse(const GraphType &G) : Graph(G) {}
};
// Provide a partial specialization of GraphTraits so that the inverse of an
// inverse falls back to the original graph.
template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {};
// Provide iterator ranges for the graph traits nodes and children
template <class GraphType>
iterator_range<typename GraphTraits<GraphType>::nodes_iterator>
nodes(const GraphType &G) {
return make_range(GraphTraits<GraphType>::nodes_begin(G),
GraphTraits<GraphType>::nodes_end(G));
}
template <class GraphType>
iterator_range<typename GraphTraits<Inverse<GraphType>>::nodes_iterator>
inverse_nodes(const GraphType &G) {
return make_range(GraphTraits<Inverse<GraphType>>::nodes_begin(G),
GraphTraits<Inverse<GraphType>>::nodes_end(G));
}
template <class GraphType>
iterator_range<typename GraphTraits<GraphType>::ChildIteratorType>
children(const typename GraphTraits<GraphType>::NodeRef &G) {
return make_range(GraphTraits<GraphType>::child_begin(G),
GraphTraits<GraphType>::child_end(G));
}
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
|