15#ifndef LLVM_ADT_DIRECTEDGRAPH_H
16#define LLVM_ADT_DIRECTEDGRAPH_H
28template <
class NodeType,
class EdgeType>
class DGEdge {
50 return const_cast<NodeType &
>(
59 bool isEqualTo(
const EdgeType &
E)
const {
return this == &
E; }
62 EdgeType &
getDerived() {
return *
static_cast<EdgeType *
>(
this); }
64 return *
static_cast<const EdgeType *
>(
this);
73template <
class NodeType,
class EdgeType>
class DGNode {
91 Edges = std::move(
N.Edges);
97 friend bool operator==(
const NodeType &M,
const NodeType &
N) {
98 return M.isEqualTo(
N);
118 assert(EL.
empty() &&
"Expected the list of edges to be empty.");
120 if (
E->getTargetNode() ==
N)
152 NodeType &
getDerived() {
return *
static_cast<NodeType *
>(
this); }
154 return *
static_cast<const NodeType *
>(
this);
161 Edges, [&
N](
const EdgeType *
E) {
return E->getTargetNode() ==
N; });
191 Nodes = std::move(
G.Nodes);
209 [&
N](
const NodeType *
Node) {
return *
Node ==
N; });
227 assert(EL.
empty() &&
"Expected the list of edges to be empty.");
232 Node->findEdgesTo(
N, TempList);
252 Node->findEdgesTo(
N, EL);
254 Node->removeEdge(*
E);
265 bool connect(NodeType &Src, NodeType &Dst, EdgeType &
E) {
268 assert((
E.getTargetNode() == Dst) &&
269 "Target of the given edge does not match Dst.");
270 return Src.addEdge(
E);
static cl::opt< ITMode > IT(cl::desc("IT block support"), cl::Hidden, cl::init(DefaultIT), cl::values(clEnumValN(DefaultIT, "arm-default-it", "Generate any type of IT block"), clEnumValN(RestrictedIT, "arm-restrict-it", "Disallow complex IT blocks")))
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallVector class.
Represent an edge in the directed graph.
DGEdge(NodeType &N)
Create an edge pointing to the given node N.
bool operator==(const DGEdge &E) const
Static polymorphism: delegate implementation (via isEqualTo) to the derived class.
bool operator!=(const DGEdge &E) const
const EdgeType & getDerived() const
const NodeType & getTargetNode() const
Retrieve the target node this edge connects to.
NodeType & getTargetNode()
void setTargetNode(const NodeType &N)
Set the target node this edge connects to.
bool isEqualTo(const EdgeType &E) const
DGEdge(const DGEdge< NodeType, EdgeType > &E)
DGEdge< NodeType, EdgeType > & operator=(const DGEdge< NodeType, EdgeType > &E)
Represent a node in the directed graph.
const_iterator begin() const
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &N)
friend bool operator==(const NodeType &M, const NodeType &N)
Static polymorphism: delegate implementation (via isEqualTo) to the derived class.
bool addEdge(EdgeType &E)
Add the given edge E to this node, if it doesn't exist already.
const_iterator end() const
void removeEdge(EdgeType &E)
Remove the given edge E from this node, if it exists.
DGNode(DGNode< NodeType, EdgeType > &&N)
const EdgeType & front() const
typename EdgeListTy::const_iterator const_iterator
bool findEdgesTo(const NodeType &N, SmallVectorImpl< EdgeType * > &EL) const
Collect in EL, all the edges from this node to N.
const EdgeListTy & getEdges() const
Retrieve the outgoing edges for the node.
const EdgeType & back() const
bool isEqualTo(const NodeType &N) const
bool hasEdgeTo(const NodeType &N) const
Test whether there is an edge that goes from this node to N.
DGNode(EdgeType &E)
Create a node with a single outgoing edge E.
void clear()
Clear the outgoing edges.
const NodeType & getDerived() const
DGNode(const DGNode< NodeType, EdgeType > &N)
friend bool operator!=(const NodeType &M, const NodeType &N)
const_iterator findEdgeTo(const NodeType &N) const
Find an edge to N.
typename EdgeListTy::iterator iterator
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &&N)
DGraphType & operator=(const DGraphType &&G)
const NodeType & front() const
const NodeType & back() const
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 ...
DGraphType & operator=(const DGraphType &G)
bool findIncomingEdgesToNode(const NodeType &N, SmallVectorImpl< EdgeType * > &EL) const
Collect in EL all edges that are coming into node N.
const_iterator begin() const
const_iterator end() const
DirectedGraph(DGraphType &&RHS)
typename NodeListTy::iterator iterator
typename NodeListTy::const_iterator const_iterator
bool addNode(NodeType &N)
Add the given node N to the graph if it is not already present.
DirectedGraph(NodeType &N)
bool removeNode(NodeType &N)
Remove the given node N from the graph.
iterator findNode(const NodeType &N)
const_iterator findNode(const NodeType &N) const
Find the given node N in the table.
DirectedGraph(const DGraphType &G)
typename vector_type::const_iterator const_iterator
bool remove(const value_type &X)
Remove an item from the set vector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
const value_type & front() const
Return the first element of the SetVector.
void clear()
Completely clear the SetVector.
typename vector_type::const_iterator iterator
const value_type & back() const
Return the last element of the SetVector.
iterator begin()
Get an iterator to the beginning of the SetVector.
iterator end()
Get an iterator to the end of the SetVector.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
iterator erase(const_iterator CI)
void push_back(const T &Elt)
This is an optimization pass for GlobalISel generic memory operations.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.