LLVM  10.0.0svn
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) {}
36  return *this;
37  }
38 
39  /// Static polymorphism: delegate implementation (via isEqualTo) to the
40  /// derived class.
41  bool operator==(const EdgeType &E) const { return getDerived().isEqualTo(E); }
42  bool operator!=(const EdgeType &E) const { return !operator==(E); }
43 
44  /// Retrieve the target node this edge connects to.
45  const NodeType &getTargetNode() const { return TargetNode; }
47  return const_cast<NodeType &>(
48  static_cast<const DGEdge<NodeType, EdgeType> &>(*this).getTargetNode());
49  }
50 
51 protected:
52  // As the default implementation use address comparison for equality.
53  bool isEqualTo(const EdgeType &E) const { return this == &E; }
54 
55  // Cast the 'this' pointer to the derived type and return a reference.
56  EdgeType &getDerived() { return *static_cast<EdgeType *>(this); }
57  const EdgeType &getDerived() const {
58  return *static_cast<const EdgeType *>(this);
59  }
60 
61  // The target node this edge connects to.
63 };
64 
65 /// Represent a node in the directed graph.
66 /// The node has a (possibly empty) list of outgoing edges.
67 template <class NodeType, class EdgeType> class DGNode {
68 public:
70  using iterator = typename EdgeListTy::iterator;
72 
73  /// Create a node with a single outgoing edge \p E.
74  explicit DGNode(EdgeType &E) : Edges() { Edges.insert(&E); }
75  DGNode() = default;
76 
77  explicit DGNode(const DGNode<NodeType, EdgeType> &N) : Edges(N.Edges) {}
78  DGNode(DGNode<NodeType, EdgeType> &&N) : Edges(std::move(N.Edges)) {}
79 
81  Edges = N.Edges;
82  return *this;
83  }
85  Edges = std::move(N.Edges);
86  return *this;
87  }
88 
89  /// Static polymorphism: delegate implementation (via isEqualTo) to the
90  /// derived class.
91  bool operator==(const NodeType &N) const { return getDerived().isEqualTo(N); }
92  bool operator!=(const NodeType &N) const { return !operator==(N); }
93 
94  const_iterator begin() const { return Edges.begin(); }
95  const_iterator end() const { return Edges.end(); }
96  iterator begin() { return Edges.begin(); }
97  iterator end() { return Edges.end(); }
98  const EdgeType &front() const { return *Edges.front(); }
99  EdgeType &front() { return *Edges.front(); }
100  const EdgeType &back() const { return *Edges.back(); }
101  EdgeType &back() { return *Edges.back(); }
102 
103  /// Collect in \p EL, all the edges from this node to \p N.
104  /// Return true if at least one edge was found, and false otherwise.
105  /// Note that this implementation allows more than one edge to connect
106  /// a given pair of nodes.
108  assert(EL.empty() && "Expected the list of edges to be empty.");
109  for (auto *E : Edges)
110  if (E->getTargetNode() == N)
111  EL.push_back(E);
112  return !EL.empty();
113  }
114 
115  /// Add the given edge \p E to this node, if it doesn't exist already. Returns
116  /// true if the edge is added and false otherwise.
117  bool addEdge(EdgeType &E) { return Edges.insert(&E); }
118 
119  /// Remove the given edge \p E from this node, if it exists.
120  void removeEdge(EdgeType &E) { Edges.remove(&E); }
121 
122  /// Test whether there is an edge that goes from this node to \p N.
123  bool hasEdgeTo(const NodeType &N) const {
124  return (findEdgeTo(N) != Edges.end());
125  }
126 
127  /// Retrieve the outgoing edges for the node.
128  const EdgeListTy &getEdges() const { return Edges; }
130  return const_cast<EdgeListTy &>(
131  static_cast<const DGNode<NodeType, EdgeType> &>(*this).Edges);
132  }
133 
134  /// Clear the outgoing edges.
135  void clear() { Edges.clear(); }
136 
137 protected:
138  // As the default implementation use address comparison for equality.
139  bool isEqualTo(const NodeType &N) const { return this == &N; }
140 
141  // Cast the 'this' pointer to the derived type and return a reference.
142  NodeType &getDerived() { return *static_cast<NodeType *>(this); }
143  const NodeType &getDerived() const {
144  return *static_cast<const NodeType *>(this);
145  }
146 
147  /// Find an edge to \p N. If more than one edge exists, this will return
148  /// the first one in the list of edges.
150  return llvm::find_if(
151  Edges, [&N](const EdgeType *E) { return E->getTargetNode() == N; });
152  }
153 
154  // The list of outgoing edges.
156 };
157 
158 /// Directed graph
159 ///
160 /// The graph is represented by a table of nodes.
161 /// Each node contains a (possibly empty) list of outgoing edges.
162 /// Each edge contains the target node it connects to.
163 template <class NodeType, class EdgeType> class DirectedGraph {
164 protected:
167 public:
168  using iterator = typename NodeListTy::iterator;
171 
172  DirectedGraph() = default;
173  explicit DirectedGraph(NodeType &N) : Nodes() { addNode(N); }
174  DirectedGraph(const DGraphType &G) : Nodes(G.Nodes) {}
175  DirectedGraph(DGraphType &&RHS) : Nodes(std::move(RHS.Nodes)) {}
177  Nodes = G.Nodes;
178  return *this;
179  }
181  Nodes = std::move(G.Nodes);
182  return *this;
183  }
184 
185  const_iterator begin() const { return Nodes.begin(); }
186  const_iterator end() const { return Nodes.end(); }
187  iterator begin() { return Nodes.begin(); }
188  iterator end() { return Nodes.end(); }
189  const NodeType &front() const { return *Nodes.front(); }
190  NodeType &front() { return *Nodes.front(); }
191  const NodeType &back() const { return *Nodes.back(); }
192  NodeType &back() { return *Nodes.back(); }
193 
194  size_t size() const { return Nodes.size(); }
195 
196  /// Find the given node \p N in the table.
198  return llvm::find_if(Nodes,
199  [&N](const NodeType *Node) { return *Node == N; });
200  }
202  return const_cast<iterator>(
203  static_cast<const DGraphType &>(*this).findNode(N));
204  }
205 
206  /// Add the given node \p N to the graph if it is not already present.
207  bool addNode(NodeType &N) {
208  if (findNode(N) != Nodes.end())
209  return false;
210  Nodes.push_back(&N);
211  return true;
212  }
213 
214  /// Collect in \p EL all edges that are coming into node \p N. Return true
215  /// if at least one edge was found, and false otherwise.
217  assert(EL.empty() && "Expected the list of edges to be empty.");
218  EdgeListTy TempList;
219  for (auto *Node : Nodes) {
220  if (*Node == N)
221  continue;
222  Node->findEdgesTo(N, TempList);
223  EL.insert(EL.end(), TempList.begin(), TempList.end());
224  TempList.clear();
225  }
226  return !EL.empty();
227  }
228 
229  /// Remove the given node \p N from the graph. If the node has incoming or
230  /// outgoing edges, they are also removed. Return true if the node was found
231  /// and then removed, and false if the node was not found in the graph to
232  /// begin with.
234  iterator IT = findNode(N);
235  if (IT == Nodes.end())
236  return false;
237  // Remove incoming edges.
238  EdgeListTy EL;
239  for (auto *Node : Nodes) {
240  if (*Node == N)
241  continue;
242  Node->findEdgesTo(N, EL);
243  for (auto *E : EL)
244  Node->removeEdge(*E);
245  EL.clear();
246  }
247  N.clear();
248  Nodes.erase(IT);
249  return true;
250  }
251 
252  /// Assuming nodes \p Src and \p Dst are already in the graph, connect node \p
253  /// Src to node \p Dst using the provided edge \p E. Return true if \p Src is
254  /// not already connected to \p Dst via \p E, and false otherwise.
255  bool connect(NodeType &Src, NodeType &Dst, EdgeType &E) {
256  assert(findNode(Src) != Nodes.end() && "Src node should be present.");
257  assert(findNode(Dst) != Nodes.end() && "Dst node should be present.");
258  assert((E.getTargetNode() == Dst) &&
259  "Target of the given edge does not match Dst.");
260  return Src.addEdge(E);
261  }
262 
263 protected:
264  // The list of nodes in the graph.
266 };
267 
268 } // namespace llvm
269 
270 #endif // LLVM_ADT_DIRECTEDGRAPH_H
DGraphType & operator=(const DGraphType &G)
const NodeType & getDerived() const
DGEdge< NodeType, EdgeType > & operator=(const DGEdge< NodeType, EdgeType > &E)
Definition: DirectedGraph.h:34
bool operator==(const NodeType &N) const
Static polymorphism: delegate implementation (via isEqualTo) to the derived class.
Definition: DirectedGraph.h:91
void clear()
Clear the outgoing edges.
iterator end()
Definition: DirectedGraph.h:97
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:320
This class represents lattice values for constants.
Definition: AllocatorList.h:23
EdgeType & front()
Definition: DirectedGraph.h:99
const EdgeType & front() const
Definition: DirectedGraph.h:98
DGEdge()=delete
EdgeType & getDerived()
Definition: DirectedGraph.h:56
const NodeType & getTargetNode() const
Retrieve the target node this edge connects to.
Definition: DirectedGraph.h:45
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &&N)
Definition: DirectedGraph.h:84
DGNode(EdgeType &E)
Create a node with a single outgoing edge E.
Definition: DirectedGraph.h:74
bool hasEdgeTo(const NodeType &N) const
Test whether there is an edge that goes from this node to N.
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
Definition: ISDOpcodes.h:38
bool addEdge(EdgeType &E)
Add the given edge E to this node, if it doesn&#39;t exist already.
EdgeListTy & getEdges()
const_iterator begin() const
Definition: BitVector.h:937
const_iterator findNode(const NodeType &N) const
Find the given node N in the table.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &N)
Definition: DirectedGraph.h:80
NodeType & getDerived()
bool isEqualTo(const EdgeType &E) const
Definition: DirectedGraph.h:53
DirectedGraph(NodeType &N)
typename EdgeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:71
bool operator!=(const EdgeType &E) const
Definition: DirectedGraph.h:42
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 ...
bool findIncomingEdgesToNode(const NodeType &N, SmallVectorImpl< EdgeType *> &EL) const
Collect in EL all edges that are coming into node N.
const EdgeListTy & getEdges() const
Retrieve the outgoing edges for the node.
bool removeNode(NodeType &N)
Remove the given node N from the graph.
bool operator!=(const NodeType &N) const
Definition: DirectedGraph.h:92
DGNode(const DGNode< NodeType, EdgeType > &N)
Definition: DirectedGraph.h:77
bool operator==(const EdgeType &E) const
Static polymorphism: delegate implementation (via isEqualTo) to the derived class.
Definition: DirectedGraph.h:41
const_iterator end() const
Definition: DirectedGraph.h:95
size_t size() const
Represent an edge in the directed graph.
Definition: DirectedGraph.h:27
const EdgeType & back() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const NodeType & front() const
DGEdge(NodeType &N)
Create an edge pointing to the given node N.
Definition: DirectedGraph.h:31
EdgeType & back()
DGNode(DGNode< NodeType, EdgeType > &&N)
Definition: DirectedGraph.h:78
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1193
DGEdge(const DGEdge< NodeType, EdgeType > &E)
Definition: DirectedGraph.h:32
NodeType & TargetNode
Definition: DirectedGraph.h:62
EdgeListTy Edges
typename vector_type::const_iterator const_iterator
Definition: SetVector.h:49
iterator findNode(const NodeType &N)
typename vector_type::const_iterator iterator
Definition: SetVector.h:48
Directed graph.
iterator begin()
Definition: DirectedGraph.h:96
DGraphType & operator=(const DGraphType &&G)
Represent a node in the directed graph.
Definition: DirectedGraph.h:67
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
NodeType & getTargetNode()
Definition: DirectedGraph.h:46
const_iterator end() const
typename SuperClass::iterator iterator
Definition: SmallVector.h:319
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:467
void removeEdge(EdgeType &E)
Remove the given edge E from this node, if it exists.
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_NODISCARD bool empty() const
Definition: SmallVector.h:55
typename EdgeListTy::iterator iterator
Definition: DirectedGraph.h:70
typename NodeListTy::const_iterator const_iterator
const_iterator findEdgeTo(const NodeType &N) const
Find an edge to N.
#define N
const NodeType & back() const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
NodeType & front()
bool findEdgesTo(const NodeType &N, SmallVectorImpl< EdgeType *> &EL) const
Collect in EL, all the edges from this node to N.
DirectedGraph(DGraphType &&RHS)
bool addNode(NodeType &N)
Add the given node N to the graph if it is not already present.
bool isEqualTo(const NodeType &N) const
A vector that has set insertion semantics.
Definition: SetVector.h:40
typename NodeListTy::iterator iterator
const EdgeType & getDerived() const
Definition: DirectedGraph.h:57
DirectedGraph(const DGraphType &G)
const_iterator begin() const
Definition: DirectedGraph.h:94