LLVM: include/llvm/ADT/GraphTraits.h Source File

LLVM 22.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
22#include "llvm/ADT/STLExtras.h"
23#include "llvm/ADT/iterator_range.h"
24
25namespace 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.
37template<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
98namespace detail {
99template <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.
105template <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//
122template <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
134template <class GraphType>
135iterator_range<typename GraphTraits<GraphType>::nodes_iterator>
140template <class GraphType>
141iterator_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
147template <class GraphType>
148iterator_range<typename GraphTraits<GraphType>::ChildIteratorType>
153
154template <class GraphType>
155iterator_range<typename GraphTraits<Inverse<GraphType>>::ChildIteratorType>
160
161template <class GraphType>
162iterator_range<typename GraphTraits<GraphType>::ChildEdgeIteratorType>
167
168} // end namespace llvm
169
170#endif // LLVM_ADT_GRAPHTRAITS_H
Unify divergent function exit nodes
G
#define G(x, y, z)
Definition MD5.cpp:56
T
#define T
This file contains some templates that are useful if you are working with the STL at all.
A range adaptor for a pair of iterators.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
Definition ClauseT.h:112
decltype(GraphTraits< T >::getNumber( std::declval< typename GraphTraits< T >::NodeRef >())) has_number_t
Definition GraphTraits.h:100
This is an optimization pass for GlobalISel generic memory operations.
Definition AddressRanges.h:18
iterator_range< typename GraphTraits< Inverse< GraphType > >::nodes_iterator > inverse_nodes(const GraphType &G)
Definition GraphTraits.h:142
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
constexpr bool GraphHasNodeNumbers
Indicate whether a GraphTraits<NodeT>::getNumber() is supported.
Definition GraphTraits.h:106
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
iterator_range< typename GraphTraits< GraphType >::ChildEdgeIteratorType > children_edges(const typename GraphTraits< GraphType >::NodeRef &G)
Definition GraphTraits.h:163
iterator_range< typename GraphTraits< Inverse< GraphType > >::ChildIteratorType > inverse_children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition GraphTraits.h:156
typename detail::detector< void, Op, Args... >::value_t is_detected
Detects if a given trait holds for some set of arguments 'Args'.
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition GraphTraits.h:149
typename GraphType::UnknownGraphTypeError NodeRef
Definition GraphTraits.h:95
const GraphType & Graph
Definition GraphTraits.h:124
Inverse(const GraphType &G)
Definition GraphTraits.h:126
Generated on for LLVM by doxygen 1.14.0

AltStyle によって変換されたページ (->オリジナル) /