LLVM  15.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 /// \file
10 /// This file defines the interface and a base class implementation for a
11 /// directed graph.
12 ///
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ADT_DIRECTEDGRAPH_H
16 #define LLVM_ADT_DIRECTEDGRAPH_H
17 
18 #include "llvm/ADT/GraphTraits.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/Support/Debug.h"
23 
24 namespace llvm {
25 
26 /// Represent an edge in the directed graph.
27 /// The edge contains the target node it connects to.
28 template <class NodeType, class EdgeType> class DGEdge {
29 public:
30  DGEdge() = delete;
31  /// Create an edge pointing to the given node \p N.
32  explicit DGEdge(NodeType &N) : TargetNode(N) {}
34  : TargetNode(E.TargetNode) {}
36  TargetNode = E.TargetNode;
37  return *this;
38  }
39 
40  /// Static polymorphism: delegate implementation (via isEqualTo) to the
41  /// derived class.
42  bool operator==(const DGEdge &E) const {
43  return getDerived().isEqualTo(E.getDerived());
44  }
45  bool operator!=(const DGEdge &E) const { return !operator==(E); }
46 
47  /// Retrieve the target node this edge connects to.
48  const NodeType &getTargetNode() const { return TargetNode; }
50  return const_cast<NodeType &>(
51  static_cast<const DGEdge<NodeType, EdgeType> &>(*this).getTargetNode());
52  }
53 
54  /// Set the target node this edge connects to.
55  void setTargetNode(const NodeType &N) { TargetNode = N; }
56 
57 protected:
58  // As the default implementation use address comparison for equality.
59  bool isEqualTo(const EdgeType &E) const { return this == &E; }
60 
61  // Cast the 'this' pointer to the derived type and return a reference.
62  EdgeType &getDerived() { return *static_cast<EdgeType *>(this); }
63  const EdgeType &getDerived() const {
64  return *static_cast<const EdgeType *>(this);
65  }
66 
67  // The target node this edge connects to.
69 };
70 
71 /// Represent a node in the directed graph.
72 /// The node has a (possibly empty) list of outgoing edges.
73 template <class NodeType, class EdgeType> class DGNode {
74 public:
76  using iterator = typename EdgeListTy::iterator;
78 
79  /// Create a node with a single outgoing edge \p E.
80  explicit DGNode(EdgeType &E) : Edges() { Edges.insert(&E); }
81  DGNode() = default;
82 
85 
87  Edges = N.Edges;
88  return *this;
89  }
91  Edges = std::move(N.Edges);
92  return *this;
93  }
94 
95  /// Static polymorphism: delegate implementation (via isEqualTo) to the
96  /// derived class.
97  friend bool operator==(const NodeType &M, const NodeType &N) {
98  return M.isEqualTo(N);
99  }
100  friend bool operator!=(const NodeType &M, const NodeType &N) {
101  return !(M == N);
102  }
103 
104  const_iterator begin() const { return Edges.begin(); }
105  const_iterator end() const { return Edges.end(); }
106  iterator begin() { return Edges.begin(); }
107  iterator end() { return Edges.end(); }
108  const EdgeType &front() const { return *Edges.front(); }
109  EdgeType &front() { return *Edges.front(); }
110  const EdgeType &back() const { return *Edges.back(); }
111  EdgeType &back() { return *Edges.back(); }
112 
113  /// Collect in \p EL, all the edges from this node to \p N.
114  /// Return true if at least one edge was found, and false otherwise.
115  /// Note that this implementation allows more than one edge to connect
116  /// a given pair of nodes.
118  assert(EL.empty() && "Expected the list of edges to be empty.");
119  for (auto *E : Edges)
120  if (E->getTargetNode() == N)
121  EL.push_back(E);
122  return !EL.empty();
123  }
124 
125  /// Add the given edge \p E to this node, if it doesn't exist already. Returns
126  /// true if the edge is added and false otherwise.
127  bool addEdge(EdgeType &E) { return Edges.insert(&E); }
128 
129  /// Remove the given edge \p E from this node, if it exists.
130  void removeEdge(EdgeType &E) { Edges.remove(&E); }
131 
132  /// Test whether there is an edge that goes from this node to \p N.
133  bool hasEdgeTo(const NodeType &N) const {
134  return (findEdgeTo(N) != Edges.end());
135  }
136 
137  /// Retrieve the outgoing edges for the node.
138  const EdgeListTy &getEdges() const { return Edges; }
140  return const_cast<EdgeListTy &>(
141  static_cast<const DGNode<NodeType, EdgeType> &>(*this).Edges);
142  }
143 
144  /// Clear the outgoing edges.
145  void clear() { Edges.clear(); }
146 
147 protected:
148  // As the default implementation use address comparison for equality.
149  bool isEqualTo(const NodeType &N) const { return this == &N; }
150 
151  // Cast the 'this' pointer to the derived type and return a reference.
152  NodeType &getDerived() { return *static_cast<NodeType *>(this); }
153  const NodeType &getDerived() const {
154  return *static_cast<const NodeType *>(this);
155  }
156 
157  /// Find an edge to \p N. If more than one edge exists, this will return
158  /// the first one in the list of edges.
160  return llvm::find_if(
161  Edges, [&N](const EdgeType *E) { return E->getTargetNode() == N; });
162  }
163 
164  // The list of outgoing edges.
166 };
167 
168 /// Directed graph
169 ///
170 /// The graph is represented by a table of nodes.
171 /// Each node contains a (possibly empty) list of outgoing edges.
172 /// Each edge contains the target node it connects to.
173 template <class NodeType, class EdgeType> class DirectedGraph {
174 protected:
177 public:
178  using iterator = typename NodeListTy::iterator;
181 
182  DirectedGraph() = default;
183  explicit DirectedGraph(NodeType &N) : Nodes() { addNode(N); }
187  Nodes = G.Nodes;
188  return *this;
189  }
191  Nodes = std::move(G.Nodes);
192  return *this;
193  }
194 
195  const_iterator begin() const { return Nodes.begin(); }
196  const_iterator end() const { return Nodes.end(); }
197  iterator begin() { return Nodes.begin(); }
198  iterator end() { return Nodes.end(); }
199  const NodeType &front() const { return *Nodes.front(); }
200  NodeType &front() { return *Nodes.front(); }
201  const NodeType &back() const { return *Nodes.back(); }
202  NodeType &back() { return *Nodes.back(); }
203 
204  size_t size() const { return Nodes.size(); }
205 
206  /// Find the given node \p N in the table.
208  return llvm::find_if(Nodes,
209  [&N](const NodeType *Node) { return *Node == N; });
210  }
212  return const_cast<iterator>(
213  static_cast<const DGraphType &>(*this).findNode(N));
214  }
215 
216  /// Add the given node \p N to the graph if it is not already present.
217  bool addNode(NodeType &N) {
218  if (findNode(N) != Nodes.end())
219  return false;
220  Nodes.push_back(&N);
221  return true;
222  }
223 
224  /// Collect in \p EL all edges that are coming into node \p N. Return true
225  /// if at least one edge was found, and false otherwise.
227  assert(EL.empty() && "Expected the list of edges to be empty.");
228  EdgeListTy TempList;
229  for (auto *Node : Nodes) {
230  if (*Node == N)
231  continue;
232  Node->findEdgesTo(N, TempList);
233  llvm::append_range(EL, TempList);
234  TempList.clear();
235  }
236  return !EL.empty();
237  }
238 
239  /// Remove the given node \p N from the graph. If the node has incoming or
240  /// outgoing edges, they are also removed. Return true if the node was found
241  /// and then removed, and false if the node was not found in the graph to
242  /// begin with.
244  iterator IT = findNode(N);
245  if (IT == Nodes.end())
246  return false;
247  // Remove incoming edges.
248  EdgeListTy EL;
249  for (auto *Node : Nodes) {
250  if (*Node == N)
251  continue;
252  Node->findEdgesTo(N, EL);
253  for (auto *E : EL)
254  Node->removeEdge(*E);
255  EL.clear();
256  }
257  N.clear();
258  Nodes.erase(IT);
259  return true;
260  }
261 
262  /// Assuming nodes \p Src and \p Dst are already in the graph, connect node \p
263  /// Src to node \p Dst using the provided edge \p E. Return true if \p Src is
264  /// not already connected to \p Dst via \p E, and false otherwise.
265  bool connect(NodeType &Src, NodeType &Dst, EdgeType &E) {
266  assert(findNode(Src) != Nodes.end() && "Src node should be present.");
267  assert(findNode(Dst) != Nodes.end() && "Dst node should be present.");
268  assert((E.getTargetNode() == Dst) &&
269  "Target of the given edge does not match Dst.");
270  return Src.addEdge(E);
271  }
272 
273 protected:
274  // The list of nodes in the graph.
276 };
277 
278 } // namespace llvm
279 
280 #endif // LLVM_ADT_DIRECTEDGRAPH_H
llvm::DGNode::clear
void clear()
Clear the outgoing edges.
Definition: DirectedGraph.h:145
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:724
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:109
llvm::DirectedGraph::DirectedGraph
DirectedGraph(NodeType &N)
Definition: DirectedGraph.h:183
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:265
llvm::DGEdge::operator==
bool operator==(const DGEdge &E) const
Static polymorphism: delegate implementation (via isEqualTo) to the derived class.
Definition: DirectedGraph.h:42
llvm::DGNode::getDerived
const NodeType & getDerived() const
Definition: DirectedGraph.h:153
llvm::DGNode::isEqualTo
bool isEqualTo(const NodeType &N) const
Definition: DirectedGraph.h:149
llvm::DGNode::DGNode
DGNode(const DGNode< NodeType, EdgeType > &N)
Definition: DirectedGraph.h:83
llvm::SmallVector< NodeType *, 10 >
llvm::DGNode
Represent a node in the directed graph.
Definition: DirectedGraph.h:73
llvm::DGNode::getDerived
NodeType & getDerived()
Definition: DirectedGraph.h:152
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:100
llvm::DirectedGraph::begin
const_iterator begin() const
Definition: DirectedGraph.h:195
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:63
llvm::DirectedGraph::DirectedGraph
DirectedGraph(const DGraphType &G)
Definition: DirectedGraph.h:184
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::DGNode::end
const_iterator end() const
Definition: DirectedGraph.h:105
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:226
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:275
llvm::DGEdge::DGEdge
DGEdge(const DGEdge< NodeType, EdgeType > &E)
Definition: DirectedGraph.h:33
llvm::DirectedGraph::const_iterator
typename NodeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:179
llvm::DGNode::DGNode
DGNode(DGNode< NodeType, EdgeType > &&N)
Definition: DirectedGraph.h:84
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:107
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:133
llvm::DirectedGraph::iterator
typename NodeListTy::iterator iterator
Definition: DirectedGraph.h:178
llvm::DirectedGraph::end
const_iterator end() const
Definition: DirectedGraph.h:196
llvm::DirectedGraph::DirectedGraph
DirectedGraph()=default
llvm::DGEdge::setTargetNode
void setTargetNode(const NodeType &N)
Set the target node this edge connects to.
Definition: DirectedGraph.h:55
llvm::DGNode::getEdges
EdgeListTy & getEdges()
Definition: DirectedGraph.h:139
llvm::DirectedGraph
Directed graph.
Definition: DirectedGraph.h:173
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
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:97
llvm::DGEdge::getDerived
EdgeType & getDerived()
Definition: DirectedGraph.h:62
llvm::DGNode::getEdges
const EdgeListTy & getEdges() const
Retrieve the outgoing edges for the node.
Definition: DirectedGraph.h:138
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:211
llvm::DGNode::begin
const_iterator begin() const
Definition: DirectedGraph.h:104
llvm::DGNode::DGNode
DGNode(EdgeType &E)
Create a node with a single outgoing edge E.
Definition: DirectedGraph.h:80
llvm::DirectedGraph::front
NodeType & front()
Definition: DirectedGraph.h:200
llvm::DGEdge::DGEdge
DGEdge(NodeType &N)
Create an edge pointing to the given node N.
Definition: DirectedGraph.h:32
llvm::DGEdge::getTargetNode
const NodeType & getTargetNode() const
Retrieve the target node this edge connects to.
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 any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
llvm::SmallVectorImpl< NodeType * >::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:559
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DGNode::operator=
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &N)
Definition: DirectedGraph.h:86
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:1663
llvm::DGNode::front
const EdgeType & front() const
Definition: DirectedGraph.h:108
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:49
llvm::DGNode::begin
iterator begin()
Definition: DirectedGraph.h:106
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1811
Node
Definition: ItaniumDemangle.h:155
llvm::DGNode::const_iterator
typename EdgeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:77
llvm::DGNode::operator=
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &&N)
Definition: DirectedGraph.h:90
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:1632
llvm::DGEdge::TargetNode
NodeType & TargetNode
Definition: DirectedGraph.h:68
llvm::SetVector::clear
void clear()
Completely clear the SetVector.
Definition: SetVector.h:220
llvm::DGNode::back
const EdgeType & back() const
Definition: DirectedGraph.h:110
std
Definition: BitVector.h:851
llvm::DirectedGraph::findNode
const_iterator findNode(const NodeType &N) const
Find the given node N in the table.
Definition: DirectedGraph.h:207
llvm::DGNode::back
EdgeType & back()
Definition: DirectedGraph.h:111
llvm::DirectedGraph::front
const NodeType & front() const
Definition: DirectedGraph.h:199
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:591
llvm::DirectedGraph::DirectedGraph
DirectedGraph(DGraphType &&RHS)
Definition: DirectedGraph.h:185
llvm::DirectedGraph::addNode
bool addNode(NodeType &N)
Add the given node N to the graph if it is not already present.
Definition: DirectedGraph.h:217
llvm::DGNode::Edges
EdgeListTy Edges
Definition: DirectedGraph.h:165
llvm::DGNode::findEdgeTo
const_iterator findEdgeTo(const NodeType &N) const
Find an edge to N.
Definition: DirectedGraph.h:159
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:197
SmallVector.h
llvm::DGEdge::isEqualTo
bool isEqualTo(const EdgeType &E) const
Definition: DirectedGraph.h:59
llvm::DGEdge::operator=
DGEdge< NodeType, EdgeType > & operator=(const DGEdge< NodeType, EdgeType > &E)
Definition: DirectedGraph.h:35
llvm::SmallVectorImpl< NodeType * >::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:558
N
#define N
llvm::DGNode::iterator
typename EdgeListTy::iterator iterator
Definition: DirectedGraph.h:76
llvm::DGNode::removeEdge
void removeEdge(EdgeType &E)
Remove the given edge E from this node, if it exists.
Definition: DirectedGraph.h:130
llvm::DirectedGraph::back
NodeType & back()
Definition: DirectedGraph.h:202
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
llvm::DirectedGraph::removeNode
bool removeNode(NodeType &N)
Remove the given node N from the graph.
Definition: DirectedGraph.h:243
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:45
llvm::DGEdge
Represent an edge in the directed graph.
Definition: DirectedGraph.h:28
llvm::DirectedGraph::back
const NodeType & back() const
Definition: DirectedGraph.h:201
llvm::DGNode::addEdge
bool addEdge(EdgeType &E)
Add the given edge E to this node, if it doesn't exist already.
Definition: DirectedGraph.h:127
llvm::DirectedGraph::operator=
DGraphType & operator=(const DGraphType &G)
Definition: DirectedGraph.h:186
raw_ostream.h
llvm::SetVector< EdgeType * >
llvm::DirectedGraph::operator=
DGraphType & operator=(const DGraphType &&G)
Definition: DirectedGraph.h:190
llvm::DirectedGraph::size
size_t size() const
Definition: DirectedGraph.h:204
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:117
llvm::DirectedGraph::end
iterator end()
Definition: DirectedGraph.h:198
SetVector.h