ImmutableGraph.h Source File (original) (raw)

25#ifndef LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H

26#define LLVM_LIB_TARGET_X86_IMMUTABLEGRAPH_H

31#include

32#include

33#include

34#include

36namespace llvm {

38template <typename NodeValueT, typename EdgeValueT> class ImmutableGraph {

42public:

51 const Node *Dest;

54 public:

57 };

62 const Edge *Edges;

65 public:

73 const Edge *edges_end() const { return (this + 1)->Edges; }

77 };

79protected:

80 ImmutableGraph(std::unique_ptr<Node[]> Nodes, std::unique_ptr<Edge[]> Edges,

82 : Nodes(std::move(Nodes)), Edges(std::move(Edges)), NodesSize(NodesSize),

83 EdgesSize(EdgesSize) {}

89public:

100

101

105

109

110

114

115 public:

120 bool AlreadyExists = V.test(Idx);

121 V.set(Idx);

122 return !AlreadyExists;

123 }

130 return V.test(Idx);

131 }

134

136

138

141 V |= RHS.V;

142 return *this;

143 }

144

147 V &= RHS.V;

148 return *this;

149 }

150

153 V ^= RHS.V;

154 return *this;

155 }

156

162

166

167 void advance() {

168 assert(Current != -1);

169 Current = Set.V.find_next(Current);

170 }

171

172 public:

174 : Set{Set}, Current{Begin} {}

177 advance();

178 return Tmp;

179 }

181 advance();

182 return *this;

183 }

185 assert(Current != -1);

186 return Set.G.nodes_begin() + Current;

187 }

189 assert(&this->Set == &other.Set);

190 return this->Current == other.Current;

191 }

193 };

194

197 };

198

202

203 public:

208 bool AlreadyExists = V.test(Idx);

209 V.set(Idx);

210 return !AlreadyExists;

211 }

218 return V.test(Idx);

219 }

221 bool empty() const { return V.none(); }

222

224

226

229 V |= RHS.V;

230 return *this;

231 }

232

235 V &= RHS.V;

236 return *this;

237 }

238

241 V ^= RHS.V;

242 return *this;

243 }

244

250

254

255 void advance() {

256 assert(Current != -1);

257 Current = Set.V.find_next(Current);

258 }

259

260 public:

262 : Set{Set}, Current{Begin} {}

265 advance();

266 return Tmp;

267 }

269 advance();

270 return *this;

271 }

273 assert(Current != -1);

274 return Set.G.edges_begin() + Current;

275 }

277 assert(&this->Set == &other.Set);

278 return this->Current == other.Current;

279 }

281 };

282

285 };

286

287private:

288 std::unique_ptr<Node[]> Nodes;

289 std::unique_ptr<Edge[]> Edges;

290 size_type NodesSize;

291 size_type EdgesSize;

292};

293

295 using node_value_type = typename GraphT::node_value_type;

296 using edge_value_type = typename GraphT::edge_value_type;

297 static_assert(

298 std::is_base_of<ImmutableGraph<node_value_type, edge_value_type>,

299 GraphT>::value,

300 "Template argument to ImmutableGraphBuilder must derive from "

301 "ImmutableGraph<>");

302 using size_type = typename GraphT::size_type;

303 using NodeSet = typename GraphT::NodeSet;

304 using Node = typename GraphT::Node;

305 using EdgeSet = typename GraphT::EdgeSet;

306 using Edge = typename GraphT::Edge;

307 using BuilderEdge = std::pair<edge_value_type, size_type>;

308 using EdgeList = std::vector;

309 using BuilderVertex = std::pair<node_value_type, EdgeList>;

310 using VertexVec = std::vector;

311

312public:

314

316 auto I = AdjList.emplace(AdjList.end(), V, EdgeList{});

317 return std::distance(AdjList.begin(), I);

318 }

319

322 AdjList[From].second.emplace_back(E, To);

323 }

324

325 bool empty() const { return AdjList.empty(); }

326

327 template <typename... ArgT> std::unique_ptr get(ArgT &&... Args) {

328 size_type VertexSize = AdjList.size(), EdgeSize = 0;

329 for (const auto &V : AdjList) {

330 EdgeSize += V.second.size();

331 }

332 auto VertexArray =

333 std::make_unique<Node[]>(VertexSize + 1 );

334 auto EdgeArray = std::make_unique<Edge[]>(EdgeSize);

335 size_type VI = 0, EI = 0;

336 for (; VI < VertexSize; ++VI) {

337 VertexArray[VI].Value = std::move(AdjList[VI].first);

338 VertexArray[VI].Edges = &EdgeArray[EI];

339 auto NumEdges = static_cast<size_type>(AdjList[VI].second.size());

340 for (size_type VEI = 0; VEI < NumEdges; ++VEI, ++EI) {

341 auto &E = AdjList[VI].second[VEI];

342 EdgeArray[EI].Value = std::move(E.first);

343 EdgeArray[EI].Dest = &VertexArray[E.second];

344 }

345 }

346 assert(VI == VertexSize && EI == EdgeSize && "ImmutableGraph malformed");

347 VertexArray[VI].Edges = &EdgeArray[EdgeSize];

348 return std::make_unique(std::move(VertexArray),

349 std::move(EdgeArray), VertexSize, EdgeSize,

350 std::forward(Args)...);

351 }

352

353 template <typename... ArgT>

354 static std::unique_ptr trim(const GraphT &G, const NodeSet &TrimNodes,

355 const EdgeSet &TrimEdges,

356 ArgT &&... Args) {

357 size_type NewVertexSize = G.nodes_size() - TrimNodes.count();

358 size_type NewEdgeSize = G.edges_size() - TrimEdges.count();

359 auto NewVertexArray =

360 std::make_unique<Node[]>(NewVertexSize + 1 );

361 auto NewEdgeArray = std::make_unique<Edge[]>(NewEdgeSize);

362

363

364 size_type NewNodeIndex = 0;

365 std::vector<size_type> RemappedNodeIndex(G.nodes_size());

366 for (const Node &N : G.nodes()) {

367 if (TrimNodes.contains(N))

368 continue;

369 RemappedNodeIndex[G.getNodeIndex(N)] = NewNodeIndex++;

370 }

371 assert(NewNodeIndex == NewVertexSize &&

372 "Should have assigned NewVertexSize indices");

373

374 size_type VertexI = 0, EdgeI = 0;

375 for (const Node &N : G.nodes()) {

376 if (TrimNodes.contains(N))

377 continue;

378 NewVertexArray[VertexI].Value = N.getValue();

379 NewVertexArray[VertexI].Edges = &NewEdgeArray[EdgeI];

380 for (const Edge &E : N.edges()) {

381 if (TrimEdges.contains(E))

382 continue;

383 NewEdgeArray[EdgeI].Value = E.getValue();

384 size_type DestIdx = G.getNodeIndex(*E.getDest());

385 size_type NewIdx = RemappedNodeIndex[DestIdx];

386 assert(NewIdx < NewVertexSize);

387 NewEdgeArray[EdgeI].Dest = &NewVertexArray[NewIdx];

388 ++EdgeI;

389 }

390 ++VertexI;

391 }

392 assert(VertexI == NewVertexSize && EdgeI == NewEdgeSize &&

393 "Gadget graph malformed");

394 NewVertexArray[VertexI].Edges = &NewEdgeArray[NewEdgeSize];

395 return std::make_unique(std::move(NewVertexArray),

396 std::move(NewEdgeArray), NewVertexSize,

397 NewEdgeSize, std::forward(Args)...);

398 }

399

400private:

401 VertexVec AdjList;

402};

403

404template <typename NodeValueT, typename EdgeValueT>

405struct GraphTraits<ImmutableGraph<NodeValueT, EdgeValueT> *> {

406 using GraphT = ImmutableGraph<NodeValueT, EdgeValueT>;

407 using NodeRef = typename GraphT::Node const *;

408 using EdgeRef = typename GraphT::Edge const &;

409

410 static NodeRef edge_dest(EdgeRef E) { return E.getDest(); }

412 mapped_iterator<typename GraphT::Edge const *, decltype(&edge_dest)>;

413

414 static NodeRef getEntryNode(GraphT *G) { return G->nodes_begin(); }

416 return {N->edges_begin(), &edge_dest};

417 }

419 return {N->edges_end(), &edge_dest};

420 }

421

423 using nodes_iterator =

425 static nodes_iterator nodes_begin(GraphT *G) {

426 return {G->nodes_begin(), &getNode};

427 }

428 static nodes_iterator nodes_end(GraphT *G) {

429 return {G->nodes_end(), &getNode};

430 }

431

432 using ChildEdgeIteratorType = typename GraphT::Edge const *;

433

434 static ChildEdgeIteratorType child_edge_begin(NodeRef N) {

435 return N->edges_begin();

436 }

437 static ChildEdgeIteratorType child_edge_end(NodeRef N) {

438 return N->edges_end();

439 }

440 static typename GraphT::size_type size(GraphT *G) { return G->nodes_size(); }

441};

442

443}

444

445#endif

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

static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)

This file implements the BitVector class.

static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")

This file defines the little GraphTraits template class that should be specialized by classes that...

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

const_set_bits_iterator_impl< BitVector > const_set_bits_iterator

Definition ImmutableGraph.h:294

size_type BuilderNodeRef

Definition ImmutableGraph.h:313

std::unique_ptr< GraphT > get(ArgT &&... Args)

Definition ImmutableGraph.h:327

BuilderNodeRef addVertex(const node_value_type &V)

Definition ImmutableGraph.h:315

void addEdge(const edge_value_type &E, BuilderNodeRef From, BuilderNodeRef To)

Definition ImmutableGraph.h:320

static std::unique_ptr< GraphT > trim(const GraphT &G, const NodeSet &TrimNodes, const EdgeSet &TrimEdges, ArgT &&... Args)

Definition ImmutableGraph.h:354

bool empty() const

Definition ImmutableGraph.h:325

Definition ImmutableGraph.h:251

iterator(const EdgeSet &Set, size_type Begin)

Definition ImmutableGraph.h:261

iterator & operator++()

Definition ImmutableGraph.h:268

iterator operator++(int)

Definition ImmutableGraph.h:263

bool operator==(const iterator &other) const

Definition ImmutableGraph.h:276

Edge * operator*() const

Definition ImmutableGraph.h:272

bool operator!=(const iterator &other) const

Definition ImmutableGraph.h:280

EdgeSet & operator&=(const EdgeSet &RHS)

Set intersection.

Definition ImmutableGraph.h:233

bool empty() const

Definition ImmutableGraph.h:221

index_iterator index_begin() const

Definition ImmutableGraph.h:246

EdgeSet(const ImmutableGraph &G, bool ContainsAll=false)

Definition ImmutableGraph.h:204

void clear()

Definition ImmutableGraph.h:220

iterator end() const

Definition ImmutableGraph.h:284

EdgeSet & operator^=(const EdgeSet &RHS)

Set disjoint union.

Definition ImmutableGraph.h:239

size_type count() const

Return the number of elements in the set.

Definition ImmutableGraph.h:223

void erase(const Edge &E)

Definition ImmutableGraph.h:212

iterator begin() const

Definition ImmutableGraph.h:283

bool contains(const Edge &E) const

Definition ImmutableGraph.h:216

bool insert(const Edge &E)

Definition ImmutableGraph.h:206

size_type size() const

Return the size of the set's domain.

Definition ImmutableGraph.h:225

EdgeSet & operator|=(const EdgeSet &RHS)

Set union.

Definition ImmutableGraph.h:227

void reset(size_type Idx)

Definition ImmutableGraph.h:249

index_iterator index_end() const

Definition ImmutableGraph.h:247

void set(size_type Idx)

Definition ImmutableGraph.h:248

typename BitVector::const_set_bits_iterator index_iterator

Definition ImmutableGraph.h:245

Definition ImmutableGraph.h:47

friend class ImmutableGraphBuilder

Definition ImmutableGraph.h:49

friend class ImmutableGraph

Definition ImmutableGraph.h:48

const edge_value_type & getValue() const

Definition ImmutableGraph.h:56

const Node * getDest() const

Definition ImmutableGraph.h:55

Definition ImmutableGraph.h:163

Node * operator*() const

Definition ImmutableGraph.h:184

iterator(const NodeSet &Set, size_type Begin)

Definition ImmutableGraph.h:173

iterator operator++(int)

Definition ImmutableGraph.h:175

bool operator!=(const iterator &other) const

Definition ImmutableGraph.h:192

iterator & operator++()

Definition ImmutableGraph.h:180

bool operator==(const iterator &other) const

Definition ImmutableGraph.h:188

NodeSet & operator^=(const NodeSet &RHS)

Set disjoint union.

Definition ImmutableGraph.h:151

iterator begin() const

Definition ImmutableGraph.h:195

NodeSet & operator&=(const NodeSet &RHS)

Set intersection.

Definition ImmutableGraph.h:145

void reset(size_type Idx)

Definition ImmutableGraph.h:161

typename BitVector::const_set_bits_iterator index_iterator

Definition ImmutableGraph.h:157

bool contains(const Node &N) const

Definition ImmutableGraph.h:128

bool insert(const Node &N)

Definition ImmutableGraph.h:118

void clear()

Definition ImmutableGraph.h:132

size_type count() const

Return the number of elements in the set.

Definition ImmutableGraph.h:135

NodeSet(const ImmutableGraph &G, bool ContainsAll=false)

Definition ImmutableGraph.h:116

NodeSet & operator|=(const NodeSet &RHS)

Set union.

Definition ImmutableGraph.h:139

index_iterator index_end() const

Definition ImmutableGraph.h:159

index_iterator index_begin() const

Definition ImmutableGraph.h:158

void set(size_type Idx)

Definition ImmutableGraph.h:160

void erase(const Node &N)

Definition ImmutableGraph.h:124

size_type size() const

Return the size of the set's domain.

Definition ImmutableGraph.h:137

size_type empty() const

Definition ImmutableGraph.h:133

iterator end() const

Definition ImmutableGraph.h:196

Definition ImmutableGraph.h:58

friend class ImmutableGraphBuilder

Definition ImmutableGraph.h:60

const Edge * edges_begin() const

Definition ImmutableGraph.h:68

const Edge * edges_end() const

Definition ImmutableGraph.h:73

const node_value_type & getValue() const

Definition ImmutableGraph.h:66

friend class ImmutableGraph

Definition ImmutableGraph.h:59

ArrayRef< Edge > edges() const

Definition ImmutableGraph.h:74

friend class ImmutableGraphBuilder

Definition ImmutableGraph.h:40

const Node * nodes_begin() const

Definition ImmutableGraph.h:91

ImmutableGraph & operator=(ImmutableGraph &&)=delete

ArrayRef< Edge > edges() const

Definition ImmutableGraph.h:94

const Node * nodes_end() const

Definition ImmutableGraph.h:92

const Edge * edges_begin() const

Definition ImmutableGraph.h:95

size_type nodes_size() const

Definition ImmutableGraph.h:98

size_type getNodeIndex(const Node &N) const

Definition ImmutableGraph.h:102

size_type getEdgeIndex(const Edge &E) const

Definition ImmutableGraph.h:106

ImmutableGraph(const ImmutableGraph &)=delete

ImmutableGraph(ImmutableGraph &&)=delete

const Edge * edges_end() const

Definition ImmutableGraph.h:96

int size_type

Definition ImmutableGraph.h:45

ImmutableGraph & operator=(const ImmutableGraph &)=delete

size_type edges_size() const

Definition ImmutableGraph.h:99

EdgeValueT edge_value_type

Definition ImmutableGraph.h:44

NodeValueT node_value_type

Definition ImmutableGraph.h:43

ImmutableGraph(std::unique_ptr< Node[]> Nodes, std::unique_ptr< Edge[]> Edges, size_type NodesSize, size_type EdgesSize)

Definition ImmutableGraph.h:80

ArrayRef< Node > nodes() const

Definition ImmutableGraph.h:90

std::pair< NodeId, LaneBitmask > NodeRef

This is an optimization pass for GlobalISel generic memory operations.

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

ArrayRef(const T &OneElt) -> ArrayRef< T >

OutputIt move(R &&Range, OutputIt Out)

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

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