DirectedGraph.h Source File (original) (raw)

15#ifndef LLVM_ADT_DIRECTEDGRAPH_H

16#define LLVM_ADT_DIRECTEDGRAPH_H

24namespace llvm {

28template <class NodeType, class EdgeType> class DGEdge {

29public:

37 return *this;

38 }

43 return getDerived().isEqualTo(E.getDerived());

44 }

50 return const_cast<NodeType &>(

52 }

57protected:

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);

65 }

69};

73template <class NodeType, class EdgeType> class DGNode {

74public:

88 return *this;

89 }

91 Edges = std::move(N.Edges);

92 return *this;

93 }

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

112

113

114

115

116

118 assert(EL.empty() && "Expected the list of edges to be empty.");

119 for (auto *E : Edges)

120 if (E->getTargetNode() == N)

122 return !EL.empty();

123 }

124

125

126

128

129

131

132

135 }

136

137

142 }

143

144

146

147protected:

148

149 bool isEqualTo(const NodeType &N) const { return this == &N; }

150

151

152 NodeType &getDerived() { return *static_cast<NodeType *>(this); }

154 return *static_cast<const NodeType *>(this);

155 }

156

157

158

161 Edges, [&N](const EdgeType *E) { return E->getTargetNode() == N; });

162 }

163

164

166};

167

168

169

170

171

172

173template <class NodeType, class EdgeType> class DirectedGraph {

174protected:

177public:

181

188 return *this;

189 }

191 Nodes = std::move(G.Nodes);

192 return *this;

193 }

194

203

205

206

209 [&N](const NodeType *Node) { return *Node == N; });

210 }

214 }

215

216

219 return false;

221 return true;

222 }

223

224

225

227 assert(EL.empty() && "Expected the list of edges to be empty.");

231 continue;

232 Node->findEdgesTo(N, TempList);

234 TempList.clear();

235 }

236 return !EL.empty();

237 }

238

239

240

241

242

246 return false;

247

251 continue;

252 Node->findEdgesTo(N, EL);

253 for (auto *E : EL)

254 Node->removeEdge(*E);

255 EL.clear();

256 }

257 N.clear();

259 return true;

260 }

261

262

263

264

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);

271 }

272

273protected:

274

276};

277

278}

279

280#endif

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 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)

bool remove(const value_type &X)

Remove an item from the set vector.

const value_type & front() const

Return the first element of the SetVector.

const value_type & back() const

Return the last element of the SetVector.

typename vector_type::const_iterator iterator

iterator end()

Get an iterator to the end of the SetVector.

typename vector_type::const_iterator const_iterator

void clear()

Completely clear the SetVector.

iterator begin()

Get an iterator to the beginning of the SetVector.

bool insert(const value_type &X)

Insert a new element into 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 range R to container C.

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.

Implement std::hash so that hash_code can be used in STL containers.