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:

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:

85 friend bool operator==(const NodeType &M, const NodeType &N) {

86 return M.isEqualTo(N);

87 }

88 friend bool operator!=(const NodeType &M, const NodeType &N) {

89 return !(M == N);

90 }

96 const EdgeType &front() const { return *Edges.front(); }

98 const EdgeType &back() const { return *Edges.back(); }

99 EdgeType &back() { return *Edges.back(); }

100

101

102

103

104

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

107 for (auto *E : Edges)

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

110 return !EL.empty();

111 }

112

113

114

116

117

119

120

124

125

131

132

134

135protected:

136

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

138

139

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

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

143 }

144

145

146

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

150 }

151

152

154};

155

156

157

158

159

160

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

162protected:

165public:

169

172

177 const NodeType &front() const { return *Nodes.front(); }

179 const NodeType &back() const { return *Nodes.back(); }

181

183

184

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

188 }

191 static_cast<const DGraphType &>(*this).findNode(N));

192 }

193

194

197 return false;

199 return true;

200 }

201

202

203

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

209 continue;

210 Node->findEdgesTo(N, TempList);

212 TempList.clear();

213 }

214 return !EL.empty();

215 }

216

217

218

219

220

224 return false;

225

229 continue;

230 Node->findEdgesTo(N, EL);

231 for (auto *E : EL)

232 Node->removeEdge(*E);

233 EL.clear();

234 }

235 N.clear();

237 return true;

238 }

239

240

241

242

243 bool connect(NodeType &Src, NodeType &Dst, EdgeType &E) {

246 assert((E.getTargetNode() == Dst) &&

247 "Target of the given edge does not match Dst.");

248 return Src.addEdge(E);

249 }

250

251protected:

252

254};

255

256}

257

258#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

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

This file implements a set that has insertion order iteration characteristics.

This file defines the SmallVector class.

DGEdge(NodeType &N)

Create an edge pointing to the given node N.

Definition DirectedGraph.h:32

bool operator==(const DGEdge &E) const

Static polymorphism: delegate implementation (via isEqualTo) to the derived class.

Definition DirectedGraph.h:42

bool operator!=(const DGEdge &E) const

Definition DirectedGraph.h:45

EdgeType & getDerived()

Definition DirectedGraph.h:62

const EdgeType & getDerived() const

Definition DirectedGraph.h:63

const NodeType & getTargetNode() const

Retrieve the target node this edge connects to.

Definition DirectedGraph.h:48

NodeType & getTargetNode()

Definition DirectedGraph.h:49

void setTargetNode(const NodeType &N)

Set the target node this edge connects to.

Definition DirectedGraph.h:55

bool isEqualTo(const EdgeType &E) const

Definition DirectedGraph.h:59

DGEdge(const DGEdge< NodeType, EdgeType > &E)

Definition DirectedGraph.h:33

DGEdge< NodeType, EdgeType > & operator=(const DGEdge< NodeType, EdgeType > &E)

Definition DirectedGraph.h:35

DDGNode & TargetNode

Definition DirectedGraph.h:68

const_iterator begin() const

Definition DirectedGraph.h:92

EdgeListTy Edges

Definition DirectedGraph.h:153

iterator end()

Definition DirectedGraph.h:95

iterator begin()

Definition DirectedGraph.h:94

friend bool operator==(const NodeType &M, const NodeType &N)

Static polymorphism: delegate implementation (via isEqualTo) to the derived class.

Definition DirectedGraph.h:85

bool addEdge(EdgeType &E)

Add the given edge E to this node, if it doesn't exist already.

Definition DirectedGraph.h:115

const_iterator end() const

Definition DirectedGraph.h:93

void removeEdge(EdgeType &E)

Remove the given edge E from this node, if it exists.

Definition DirectedGraph.h:118

const EdgeType & front() const

Definition DirectedGraph.h:96

EdgeType & front()

Definition DirectedGraph.h:97

SetVector< EdgeType * > EdgeListTy

Definition DirectedGraph.h:75

typename EdgeListTy::const_iterator const_iterator

Definition DirectedGraph.h:77

bool findEdgesTo(const NodeType &N, SmallVectorImpl< EdgeType * > &EL) const

Collect in EL, all the edges from this node to N.

Definition DirectedGraph.h:105

const EdgeListTy & getEdges() const

Retrieve the outgoing edges for the node.

Definition DirectedGraph.h:126

const EdgeType & back() const

Definition DirectedGraph.h:98

bool isEqualTo(const NodeType &N) const

Definition DirectedGraph.h:137

EdgeType & back()

Definition DirectedGraph.h:99

bool hasEdgeTo(const NodeType &N) const

Test whether there is an edge that goes from this node to N.

Definition DirectedGraph.h:121

DGNode(EdgeType &E)

Create a node with a single outgoing edge E.

Definition DirectedGraph.h:80

void clear()

Clear the outgoing edges.

Definition DirectedGraph.h:133

const NodeType & getDerived() const

Definition DirectedGraph.h:141

EdgeListTy & getEdges()

Definition DirectedGraph.h:127

NodeType & getDerived()

Definition DirectedGraph.h:140

friend bool operator!=(const NodeType &M, const NodeType &N)

Definition DirectedGraph.h:88

const_iterator findEdgeTo(const NodeType &N) const

Find an edge to N.

Definition DirectedGraph.h:147

typename EdgeListTy::iterator iterator

Definition DirectedGraph.h:76

const NodeType & front() const

Definition DirectedGraph.h:177

NodeListTy Nodes

Definition DirectedGraph.h:253

iterator begin()

Definition DirectedGraph.h:175

iterator end()

Definition DirectedGraph.h:176

size_t size() const

Definition DirectedGraph.h:182

NodeType & back()

Definition DirectedGraph.h:180

const NodeType & back() const

Definition DirectedGraph.h:179

NodeType & front()

Definition DirectedGraph.h:178

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:243

SmallVector< NodeType *, 10 > NodeListTy

Definition DirectedGraph.h:163

bool findIncomingEdgesToNode(const NodeType &N, SmallVectorImpl< EdgeType * > &EL) const

Collect in EL all edges that are coming into node N.

Definition DirectedGraph.h:204

const_iterator begin() const

Definition DirectedGraph.h:173

const_iterator end() const

Definition DirectedGraph.h:174

typename NodeListTy::iterator iterator

Definition DirectedGraph.h:166

typename NodeListTy::const_iterator const_iterator

Definition DirectedGraph.h:167

DirectedGraph< NodeType, EdgeType > DGraphType

Definition DirectedGraph.h:168

bool addNode(NodeType &N)

Add the given node N to the graph if it is not already present.

Definition DirectedGraph.h:195

DirectedGraph(NodeType &N)

Definition DirectedGraph.h:171

bool removeNode(NodeType &N)

Remove the given node N from the graph.

Definition DirectedGraph.h:221

SmallVector< EdgeType *, 10 > EdgeListTy

Definition DirectedGraph.h:164

iterator findNode(const NodeType &N)

Definition DirectedGraph.h:189

const_iterator findNode(const NodeType &N) const

Find the given node N in the table.

Definition DirectedGraph.h:185

A vector that has set insertion semantics.

typename vector_type::const_iterator iterator

typename vector_type::const_iterator const_iterator

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

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.

auto find_if(R &&Range, UnaryPredicate P)

Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.