LLVM  14.0.0git
DirectedGraph.h
Go to the documentation of this file.
1 //===- llvm/ADT/DirectedGraph.h - Directed Graph ----------------*- 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 // This file defines the interface and a base class implementation for a
10 // directed graph.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ADT_DIRECTEDGRAPH_H
15 #define LLVM_ADT_DIRECTEDGRAPH_H
16 
17 #include "llvm/ADT/GraphTraits.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/Support/Debug.h"
22 
23 namespace llvm {
24 
25 /// Represent an edge in the directed graph.
26 /// The edge contains the target node it connects to.
27 template <class NodeType, class EdgeType> class DGEdge {
28 public:
29  DGEdge() = delete;
30  /// Create an edge pointing to the given node \p N.
31  explicit DGEdge(NodeType &N) : TargetNode(N) {}
33  : TargetNode(E.TargetNode) {}
35  TargetNode = E.TargetNode;
36  return *this;
37  }
38 
39  /// Static polymorphism: delegate implementation (via isEqualTo) to the
40  /// derived class.
41  bool operator==(const DGEdge &E) const {
42  return getDerived().isEqualTo(E.getDerived());
43  }
44  bool operator!=(const DGEdge &E) const { return !operator==(E); }
45 
46  /// Retrieve the target node this edge connects to.
47  const NodeType &getTargetNode() const { return TargetNode; }
49  return const_cast<NodeType &>(
50  static_cast<const DGEdge<NodeType, EdgeType> &>(*this).getTargetNode());
51  }
52 
53  /// Set the target node this edge connects to.
54  void setTargetNode(const NodeType &N) { TargetNode = N; }
55 
56 protected:
57  // As the default implementation use address comparison for equality.
58  bool isEqualTo(const EdgeType &E) const { return this == &E; }
59 
60  // Cast the 'this' pointer to the derived type and return a reference.
61  EdgeType &getDerived() { return *static_cast<EdgeType *>(this); }
62  const EdgeType &getDerived() const {
63  return *static_cast<const EdgeType *>(this);
64  }
65 
66  // The target node this edge connects to.
68 };
69 
70 /// Represent a node in the directed graph.
71 /// The node has a (possibly empty) list of outgoing edges.
72 template <class NodeType, class EdgeType> class DGNode {
73 public:
75  using iterator = typename EdgeListTy::iterator;
77 
78  /// Create a node with a single outgoing edge \p E.
79  explicit DGNode(EdgeType &E) : Edges() { Edges.insert(&E); }
80  DGNode() = default;
81 
84 
86  Edges = N.Edges;
87  return *this;
88  }
90  Edges = std::move(N.Edges);
91  return *this;
92  }
93 
94  /// Static polymorphism: delegate implementation (via isEqualTo) to the
95  /// derived class.
96  friend bool operator==(const NodeType &M, const NodeType &N) {
97  return M.isEqualTo(N);
98  }
99  friend bool operator!=(const NodeType &M, const NodeType &N) {
100  return !(M == N);
101  }
102 
103  const_iterator begin() const { return Edges.begin(); }
104  const_iterator end() const { return Edges.end(); }
105  iterator begin() { return Edges.begin(); }
106  iterator end() { return Edges.end(); }
107  const EdgeType &front() const { return *Edges.front(); }
108  EdgeType &front() { return *Edges.front(); }
109  const EdgeType &back() const { return *Edges.back(); }
110  EdgeType &back() { return *Edges.back(); }
111 
112  /// Collect in \p EL, all the edges from this node to \p N.
113  /// Return true if at least one edge was found, and false otherwise.
114  /// Note that this implementation allows more than one edge to connect
115  /// a given pair of nodes.
117  assert(EL.empty() && "Expected the list of edges to be empty.");
118  for (auto *E : Edges)
119  if (E->getTargetNode() == N)
120  EL.push_back(E);
121  return !EL.empty();
122  }
123 
124  /// Add the given edge \p E to this node, if it doesn't exist already. Returns
125  /// true if the edge is added and false otherwise.
126  bool addEdge(EdgeType &E) { return Edges.insert(&E); }
127 
128  /// Remove the given edge \p E from this node, if it exists.
129  void removeEdge(EdgeType &E) { Edges.remove(&E); }
130 
131  /// Test whether there is an edge that goes from this node to \p N.
132  bool hasEdgeTo(const NodeType &N) const {
133  return (findEdgeTo(N) != Edges.end());
134  }
135 
136  /// Retrieve the outgoing edges for the node.
137  const EdgeListTy &getEdges() const { return Edges; }
139  return const_cast<EdgeListTy &>(
140  static_cast<const DGNode<NodeType, EdgeType> &>(*this).Edges);
141  }
142 
143  /// Clear the outgoing edges.
144  void clear() { Edges.clear(); }
145 
146 protected:
147  // As the default implementation use address comparison for equality.
148  bool isEqualTo(const NodeType &N) const { return this == &N; }
149 
150  // Cast the 'this' pointer to the derived type and return a reference.
151  NodeType &getDerived() { return *static_cast<NodeType *>(this); }
152  const NodeType &getDerived() const {
153  return *static_cast<const NodeType *>(this);
154  }
155 
156  /// Find an edge to \p N. If more than one edge exists, this will return
157  /// the first one in the list of edges.
159  return llvm::find_if(
160  Edges, [&N](const EdgeType *E) { return E->getTargetNode() == N; });
161  }
162 
163  // The list of outgoing edges.
165 };
166 
167 /// Directed graph
168 ///
169 /// The graph is represented by a table of nodes.
170 /// Each node contains a (possibly empty) list of outgoing edges.
171 /// Each edge contains the target node it connects to.
172 template <class NodeType, class EdgeType> class DirectedGraph {
173 protected:
176 public:
177  using iterator = typename NodeListTy::iterator;
180 
181  DirectedGraph() = default;
182  explicit DirectedGraph(NodeType &N) : Nodes() { addNode(N); }
186  Nodes = G.Nodes;
187  return *this;
188  }
190  Nodes = std::move(G.Nodes);
191  return *this;
192  }
193 
194  const_iterator begin() const { return Nodes.begin(); }
195  const_iterator end() const { return Nodes.end(); }
196  iterator begin() { return Nodes.begin(); }
197  iterator end() { return Nodes.end(); }
198  const NodeType &front() const { return *Nodes.front(); }
199  NodeType &front() { return *Nodes.front(); }
200  const NodeType &back() const { return *Nodes.back(); }
201  NodeType &back() { return *Nodes.back(); }
202 
203  size_t size() const { return Nodes.size(); }
204 
205  /// Find the given node \p N in the table.
207  return llvm::find_if(Nodes,
208  [&N](const NodeType *Node) { return *Node == N; });
209  }
211  return const_cast<iterator>(
212  static_cast<const DGraphType &>(*this).findNode(N));
213  }
214 
215  /// Add the given node \p N to the graph if it is not already present.
216  bool addNode(NodeType &N) {
217  if (findNode(N) != Nodes.end())
218  return false;
219  Nodes.push_back(&N);
220  return true;
221  }
222 
223  /// Collect in \p EL all edges that are coming into node \p N. Return true
224  /// if at least one edge was found, and false otherwise.
226  assert(EL.empty() && "Expected the list of edges to be empty.");
227  EdgeListTy TempList;
228  for (auto *Node : Nodes) {
229  if (*Node == N)
230  continue;
231  Node->findEdgesTo(N, TempList);
232  llvm::append_range(EL, TempList);
233  TempList.clear();
234  }
235  return !EL.empty();
236  }
237 
238  /// Remove the given node \p N from the graph. If the node has incoming or
239  /// outgoing edges, they are also removed. Return true if the node was found
240  /// and then removed, and false if the node was not found in the graph to
241  /// begin with.
243  iterator IT = findNode(N);
244  if (IT == Nodes.end())
245  return false;
246  // Remove incoming edges.
247  EdgeListTy EL;
248  for (auto *Node : Nodes) {
249  if (*Node == N)
250  continue;
251  Node->findEdgesTo(N, EL);
252  for (auto *E : EL)
253  Node->removeEdge(*E);
254  EL.clear();
255  }
256  N.clear();
257  Nodes.erase(IT);
258  return true;
259  }
260 
261  /// Assuming nodes \p Src and \p Dst are already in the graph, connect node \p
262  /// Src to node \p Dst using the provided edge \p E. Return true if \p Src is
263  /// not already connected to \p Dst via \p E, and false otherwise.
264  bool connect(NodeType &Src, NodeType &Dst, EdgeType &E) {
265  assert(findNode(Src) != Nodes.end() && "Src node should be present.");
266  assert(findNode(Dst) != Nodes.end() && "Dst node should be present.");
267  assert((E.getTargetNode() == Dst) &&
268  "Target of the given edge does not match Dst.");
269  return Src.addEdge(E);
270  }
271 
272 protected:
273  // The list of nodes in the graph.
275 };
276 
277 } // namespace llvm
278 
279 #endif // LLVM_ADT_DIRECTEDGRAPH_H
llvm::DGNode::clear
void clear()
Clear the outgoing edges.
Definition: DirectedGraph.h:144
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:705
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::DGNode::front
EdgeType & front()
Definition: DirectedGraph.h:108
llvm::DirectedGraph::DirectedGraph
DirectedGraph(NodeType &N)
Definition: DirectedGraph.h:182
llvm::DirectedGraph::connect
bool connect(NodeType &Src, NodeType &Dst, EdgeType &E)
Assuming nodes Src and Dst are already in the graph, connect node Src to node Dst using the provided ...
Definition: DirectedGraph.h:264
llvm::DGEdge::operator==
bool operator==(const DGEdge &E) const
Static polymorphism: delegate implementation (via isEqualTo) to the derived class.
Definition: DirectedGraph.h:41
llvm::DGNode::getDerived
const NodeType & getDerived() const
Definition: DirectedGraph.h:152
llvm::DGNode::isEqualTo
bool isEqualTo(const NodeType &N) const
Definition: DirectedGraph.h:148
llvm::DGNode::DGNode
DGNode(const DGNode< NodeType, EdgeType > &N)
Definition: DirectedGraph.h:82
llvm::SmallVector< NodeType *, 10 >
llvm::DGNode
Represent a node in the directed graph.
Definition: DirectedGraph.h:72
llvm::DGNode::getDerived
NodeType & getDerived()
Definition: DirectedGraph.h:151
llvm::SetVector< EdgeType * >::iterator
typename vector_type::const_iterator iterator
Definition: SetVector.h:48
llvm::DGNode::operator!=
friend bool operator!=(const NodeType &M, const NodeType &N)
Definition: DirectedGraph.h:99
llvm::DirectedGraph::begin
const_iterator begin() const
Definition: DirectedGraph.h:194
llvm::SetVector< EdgeType * >::const_iterator
typename vector_type::const_iterator const_iterator
Definition: SetVector.h:49
llvm::DGEdge::getDerived
const EdgeType & getDerived() const
Definition: DirectedGraph.h:62
llvm::DirectedGraph::DirectedGraph
DirectedGraph(const DGraphType &G)
Definition: DirectedGraph.h:183
llvm::DGNode::end
const_iterator end() const
Definition: DirectedGraph.h:104
llvm::DirectedGraph::findIncomingEdgesToNode
bool findIncomingEdgesToNode(const NodeType &N, SmallVectorImpl< EdgeType * > &EL) const
Collect in EL all edges that are coming into node N.
Definition: DirectedGraph.h:225
GraphTraits.h
llvm::SetVector::remove
bool remove(const value_type &X)
Remove an item from the set vector.
Definition: SetVector.h:157
llvm::DirectedGraph::Nodes
NodeListTy Nodes
Definition: DirectedGraph.h:274
llvm::DGEdge::DGEdge
DGEdge(const DGEdge< NodeType, EdgeType > &E)
Definition: DirectedGraph.h:32
llvm::DirectedGraph::const_iterator
typename NodeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:178
llvm::DGNode::DGNode
DGNode(DGNode< NodeType, EdgeType > &&N)
Definition: DirectedGraph.h:83
llvm::SetVector::begin
iterator begin()
Get an iterator to the beginning of the SetVector.
Definition: SetVector.h:82
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::DGNode::DGNode
DGNode()=default
llvm::DGNode::end
iterator end()
Definition: DirectedGraph.h:106
llvm::ISD::NodeType
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
Definition: ISDOpcodes.h:40
llvm::DGNode::hasEdgeTo
bool hasEdgeTo(const NodeType &N) const
Test whether there is an edge that goes from this node to N.
Definition: DirectedGraph.h:132
llvm::DirectedGraph::iterator
typename NodeListTy::iterator iterator
Definition: DirectedGraph.h:177
llvm::DirectedGraph::end
const_iterator end() const
Definition: DirectedGraph.h:195
llvm::DirectedGraph::DirectedGraph
DirectedGraph()=default
llvm::DGEdge::setTargetNode
void setTargetNode(const NodeType &N)
Set the target node this edge connects to.
Definition: DirectedGraph.h:54
llvm::DGNode::getEdges
EdgeListTy & getEdges()
Definition: DirectedGraph.h:138
llvm::DirectedGraph
Directed graph.
Definition: DirectedGraph.h:172
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::DGNode::operator==
friend bool operator==(const NodeType &M, const NodeType &N)
Static polymorphism: delegate implementation (via isEqualTo) to the derived class.
Definition: DirectedGraph.h:96
llvm::DGEdge::getDerived
EdgeType & getDerived()
Definition: DirectedGraph.h:61
llvm::DGNode::getEdges
const EdgeListTy & getEdges() const
Retrieve the outgoing edges for the node.
Definition: DirectedGraph.h:137
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DirectedGraph::findNode
iterator findNode(const NodeType &N)
Definition: DirectedGraph.h:210
llvm::DGNode::begin
const_iterator begin() const
Definition: DirectedGraph.h:103
llvm::DGNode::DGNode
DGNode(EdgeType &E)
Create a node with a single outgoing edge E.
Definition: DirectedGraph.h:79
llvm::DirectedGraph::front
NodeType & front()
Definition: DirectedGraph.h:199
llvm::DGEdge::DGEdge
DGEdge(NodeType &N)
Create an edge pointing to the given node N.
Definition: DirectedGraph.h:31
llvm::DGEdge::getTargetNode
const NodeType & getTargetNode() const
Retrieve the target node this edge connects to.
Definition: DirectedGraph.h:47
llvm::SmallVectorImpl< NodeType * >::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:563
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DGNode::operator=
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &N)
Definition: DirectedGraph.h:85
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1605
llvm::DGNode::front
const EdgeType & front() const
Definition: DirectedGraph.h:107
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::DGEdge::getTargetNode
NodeType & getTargetNode()
Definition: DirectedGraph.h:48
IT
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::ZeroOrMore, cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate IT block based on arch"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow deprecated IT based on ARMv8"), clEnumValN(NoRestrictedIT, "arm-no-restrict-it", "Allow IT blocks based on ARMv7")))
llvm::DGNode::begin
iterator begin()
Definition: DirectedGraph.h:105
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1744
Node
Definition: ItaniumDemangle.h:234
llvm::DGNode::const_iterator
typename EdgeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:76
llvm::DGNode::operator=
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &&N)
Definition: DirectedGraph.h:89
llvm::find_if
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1574
llvm::DGEdge::TargetNode
NodeType & TargetNode
Definition: DirectedGraph.h:67
llvm::SetVector::clear
void clear()
Completely clear the SetVector.
Definition: SetVector.h:220
llvm::DGNode::back
const EdgeType & back() const
Definition: DirectedGraph.h:109
std
Definition: BitVector.h:838
llvm::DirectedGraph::findNode
const_iterator findNode(const NodeType &N) const
Find the given node N in the table.
Definition: DirectedGraph.h:206
llvm::DGNode::back
EdgeType & back()
Definition: DirectedGraph.h:110
llvm::DirectedGraph::front
const NodeType & front() const
Definition: DirectedGraph.h:198
llvm::SetVector::front
const T & front() const
Return the first element of the SetVector.
Definition: SetVector.h:122
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:585
llvm::DirectedGraph::DirectedGraph
DirectedGraph(DGraphType &&RHS)
Definition: DirectedGraph.h:184
llvm::DirectedGraph::addNode
bool addNode(NodeType &N)
Add the given node N to the graph if it is not already present.
Definition: DirectedGraph.h:216
llvm::DGNode::Edges
EdgeListTy Edges
Definition: DirectedGraph.h:164
llvm::DGNode::findEdgeTo
const_iterator findEdgeTo(const NodeType &N) const
Find an edge to N.
Definition: DirectedGraph.h:158
llvm::DGEdge::DGEdge
DGEdge()=delete
llvm::SetVector::end
iterator end()
Get an iterator to the end of the SetVector.
Definition: SetVector.h:92
llvm::DirectedGraph::begin
iterator begin()
Definition: DirectedGraph.h:196
SmallVector.h
llvm::DGEdge::isEqualTo
bool isEqualTo(const EdgeType &E) const
Definition: DirectedGraph.h:58
llvm::DGEdge::operator=
DGEdge< NodeType, EdgeType > & operator=(const DGEdge< NodeType, EdgeType > &E)
Definition: DirectedGraph.h:34
llvm::SmallVectorImpl< NodeType * >::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:562
N
#define N
llvm::DGNode::iterator
typename EdgeListTy::iterator iterator
Definition: DirectedGraph.h:75
llvm::DGNode::removeEdge
void removeEdge(EdgeType &E)
Remove the given edge E from this node, if it exists.
Definition: DirectedGraph.h:129
llvm::DirectedGraph::back
NodeType & back()
Definition: DirectedGraph.h:201
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::DirectedGraph::removeNode
bool removeNode(NodeType &N)
Remove the given node N from the graph.
Definition: DirectedGraph.h:242
llvm::SetVector::back
const T & back() const
Return the last element of the SetVector.
Definition: SetVector.h:128
llvm::DGEdge::operator!=
bool operator!=(const DGEdge &E) const
Definition: DirectedGraph.h:44
llvm::DGEdge
Represent an edge in the directed graph.
Definition: DirectedGraph.h:27
llvm::DirectedGraph::back
const NodeType & back() const
Definition: DirectedGraph.h:200
llvm::DGNode::addEdge
bool addEdge(EdgeType &E)
Add the given edge E to this node, if it doesn't exist already.
Definition: DirectedGraph.h:126
llvm::DirectedGraph::operator=
DGraphType & operator=(const DGraphType &G)
Definition: DirectedGraph.h:185
raw_ostream.h
llvm::SetVector< EdgeType * >
llvm::DirectedGraph::operator=
DGraphType & operator=(const DGraphType &&G)
Definition: DirectedGraph.h:189
llvm::DirectedGraph::size
size_t size() const
Definition: DirectedGraph.h:203
Debug.h
llvm::DGNode::findEdgesTo
bool findEdgesTo(const NodeType &N, SmallVectorImpl< EdgeType * > &EL) const
Collect in EL, all the edges from this node to N.
Definition: DirectedGraph.h:116
llvm::DirectedGraph::end
iterator end()
Definition: DirectedGraph.h:197
SetVector.h