LLVM 17.0.0git
DDG.h
Go to the documentation of this file.
1//===- llvm/Analysis/DDG.h --------------------------------------*- 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 Data-Dependence Graph (DDG).
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ANALYSIS_DDG_H
14#define LLVM_ANALYSIS_DDG_H
15
16#include "llvm/ADT/DenseMap.h"
21
22namespace llvm {
23class Function;
24class Loop;
25class LoopInfo;
26class DDGNode;
27class DDGEdge;
31class LPMUpdater;
32
33/// Data Dependence Graph Node
34/// The graph can represent the following types of nodes:
35/// 1. Single instruction node containing just one instruction.
36/// 2. Multiple instruction node where two or more instructions from
37/// the same basic block are merged into one node.
38/// 3. Pi-block node which is a group of other DDG nodes that are part of a
39/// strongly-connected component of the graph.
40/// A pi-block node contains more than one single or multiple instruction
41/// nodes. The root node cannot be part of a pi-block.
42/// 4. Root node is a special node that connects to all components such that
43/// there is always a path from it to any node in the graph.
44class DDGNode : public DDGNodeBase {
45public:
47
48 enum class NodeKind {
49 Unknown,
52 PiBlock,
53 Root,
54 };
55
56 DDGNode() = delete;
57 DDGNode(const NodeKind K) : Kind(K) {}
58 DDGNode(const DDGNode &N) = default;
59 DDGNode(DDGNode &&N) : DDGNodeBase(std::move(N)), Kind(N.Kind) {}
60 virtual ~DDGNode() = 0;
61
64 Kind = N.Kind;
65 return *this;
66 }
67
69 DGNode::operator=(std::move(N));
70 Kind = N.Kind;
71 return *this;
72 }
73
74 /// Getter for the kind of this node.
75 NodeKind getKind() const { return Kind; }
76
77 /// Collect a list of instructions, in \p IList, for which predicate \p Pred
78 /// evaluates to true when iterating over instructions of this node. Return
79 /// true if at least one instruction was collected, and false otherwise.
80 bool collectInstructions(llvm::function_ref<bool(Instruction *)> const &Pred,
81 InstructionListType &IList) const;
82
83protected:
84 /// Setter for the kind of this node.
85 void setKind(NodeKind K) { Kind = K; }
86
87private:
88 NodeKind Kind;
89};
90
91/// Subclass of DDGNode representing the root node of the graph.
92/// There should only be one such node in a given graph.
93class RootDDGNode : public DDGNode {
94public:
96 RootDDGNode(const RootDDGNode &N) = delete;
98 ~RootDDGNode() = default;
99
100 /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
101 static bool classof(const DDGNode *N) {
102 return N->getKind() == NodeKind::Root;
103 }
104 static bool classof(const RootDDGNode *N) { return true; }
105};
106
107/// Subclass of DDGNode representing single or multi-instruction nodes.
108class SimpleDDGNode : public DDGNode {
109 friend class DDGBuilder;
110
111public:
112 SimpleDDGNode() = delete;
117
119
121 DDGNode::operator=(std::move(N));
122 InstList = std::move(N.InstList);
123 return *this;
124 }
125
126 /// Get the list of instructions in this node.
128 assert(!InstList.empty() && "Instruction List is empty.");
129 return InstList;
130 }
132 return const_cast<InstructionListType &>(
133 static_cast<const SimpleDDGNode *>(this)->getInstructions());
134 }
135
136 /// Get the first/last instruction in the node.
139
140 /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
141 static bool classof(const DDGNode *N) {
142 return N->getKind() == NodeKind::SingleInstruction ||
143 N->getKind() == NodeKind::MultiInstruction;
144 }
145 static bool classof(const SimpleDDGNode *N) { return true; }
146
147private:
148 /// Append the list of instructions in \p Input to this node.
149 void appendInstructions(const InstructionListType &Input) {
150 setKind((InstList.size() == 0 && Input.size() == 1)
153 llvm::append_range(InstList, Input);
154 }
155 void appendInstructions(const SimpleDDGNode &Input) {
156 appendInstructions(Input.getInstructions());
157 }
158
159 /// List of instructions associated with a single or multi-instruction node.
160 SmallVector<Instruction *, 2> InstList;
161};
162
163/// Subclass of DDGNode representing a pi-block. A pi-block represents a group
164/// of DDG nodes that are part of a strongly-connected component of the graph.
165/// Replacing all the SCCs with pi-blocks results in an acyclic representation
166/// of the DDG. For example if we have:
167/// {a -> b}, {b -> c, d}, {c -> a}
168/// the cycle a -> b -> c -> a is abstracted into a pi-block "p" as follows:
169/// {p -> d} with "p" containing: {a -> b}, {b -> c}, {c -> a}
170class PiBlockDDGNode : public DDGNode {
171public:
173
174 PiBlockDDGNode() = delete;
179
181
183 DDGNode::operator=(std::move(N));
184 NodeList = std::move(N.NodeList);
185 return *this;
186 }
187
188 /// Get the list of nodes in this pi-block.
189 const PiNodeList &getNodes() const {
190 assert(!NodeList.empty() && "Node list is empty.");
191 return NodeList;
192 }
194 return const_cast<PiNodeList &>(
195 static_cast<const PiBlockDDGNode *>(this)->getNodes());
196 }
197
198 /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
199 static bool classof(const DDGNode *N) {
200 return N->getKind() == NodeKind::PiBlock;
201 }
202
203private:
204 /// List of nodes in this pi-block.
206};
207
208/// Data Dependency Graph Edge.
209/// An edge in the DDG can represent a def-use relationship or
210/// a memory dependence based on the result of DependenceAnalysis.
211/// A rooted edge connects the root node to one of the components
212/// of the graph.
213class DDGEdge : public DDGEdgeBase {
214public:
215 /// The kind of edge in the DDG
216 enum class EdgeKind {
217 Unknown,
220 Rooted,
221 Last = Rooted // Must be equal to the largest enum value.
222 };
223
224 explicit DDGEdge(DDGNode &N) = delete;
225 DDGEdge(DDGNode &N, EdgeKind K) : DDGEdgeBase(N), Kind(K) {}
226 DDGEdge(const DDGEdge &E) : DDGEdgeBase(E), Kind(E.getKind()) {}
227 DDGEdge(DDGEdge &&E) : DDGEdgeBase(std::move(E)), Kind(E.Kind) {}
228 DDGEdge &operator=(const DDGEdge &E) = default;
229
231 DDGEdgeBase::operator=(std::move(E));
232 Kind = E.Kind;
233 return *this;
234 }
235
236 /// Get the edge kind
237 EdgeKind getKind() const { return Kind; };
238
239 /// Return true if this is a def-use edge, and false otherwise.
240 bool isDefUse() const { return Kind == EdgeKind::RegisterDefUse; }
241
242 /// Return true if this is a memory dependence edge, and false otherwise.
243 bool isMemoryDependence() const { return Kind == EdgeKind::MemoryDependence; }
244
245 /// Return true if this is an edge stemming from the root node, and false
246 /// otherwise.
247 bool isRooted() const { return Kind == EdgeKind::Rooted; }
248
249private:
250 EdgeKind Kind;
251};
252
253/// Encapsulate some common data and functionality needed for different
254/// variations of data dependence graphs.
255template <typename NodeType> class DependenceGraphInfo {
256public:
258
261 DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
262 : Name(N), DI(DepInfo), Root(nullptr) {}
264 : Name(std::move(G.Name)), DI(std::move(G.DI)), Root(G.Root) {}
265 virtual ~DependenceGraphInfo() = default;
266
267 /// Return the label that is used to name this graph.
268 StringRef getName() const { return Name; }
269
270 /// Return the root node of the graph.
271 NodeType &getRoot() const {
272 assert(Root && "Root node is not available yet. Graph construction may "
273 "still be in progress\n");
274 return *Root;
275 }
276
277 /// Collect all the data dependency infos coming from any pair of memory
278 /// accesses from \p Src to \p Dst, and store them into \p Deps. Return true
279 /// if a dependence exists, and false otherwise.
280 bool getDependencies(const NodeType &Src, const NodeType &Dst,
281 DependenceList &Deps) const;
282
283 /// Return a string representing the type of dependence that the dependence
284 /// analysis identified between the two given nodes. This function assumes
285 /// that there is a memory dependence between the given two nodes.
286 std::string getDependenceString(const NodeType &Src,
287 const NodeType &Dst) const;
288
289protected:
290 // Name of the graph.
291 std::string Name;
292
293 // Store a copy of DependenceInfo in the graph, so that individual memory
294 // dependencies don't need to be stored. Instead when the dependence is
295 // queried it is recomputed using @DI.
297
298 // A special node in the graph that has an edge to every connected component of
299 // the graph, to ensure all nodes are reachable in a graph walk.
300 NodeType *Root = nullptr;
301};
302
304
305/// Data Dependency Graph
306class DataDependenceGraph : public DDGBase, public DDGInfo {
308 friend class DDGBuilder;
309
310public:
313
317 : DDGBase(std::move(G)), DDGInfo(std::move(G)) {}
321
322 /// If node \p N belongs to a pi-block return a pointer to the pi-block,
323 /// otherwise return null.
324 const PiBlockDDGNode *getPiBlock(const NodeType &N) const;
325
326protected:
327 /// Add node \p N to the graph, if it's not added yet, and keep track of the
328 /// root node as well as pi-blocks and their members. Return true if node is
329 /// successfully added.
330 bool addNode(NodeType &N);
331
332private:
334
335 /// Mapping from graph nodes to their containing pi-blocks. If a node is not
336 /// part of a pi-block, it will not appear in this map.
337 PiBlockMapType PiBlockMap;
338};
339
340/// Concrete implementation of a pure data dependence graph builder. This class
341/// provides custom implementation for the pure-virtual functions used in the
342/// generic dependence graph build algorithm.
343///
344/// For information about time complexity of the build algorithm see the
345/// comments near the declaration of AbstractDependenceGraphBuilder.
346class DDGBuilder : public AbstractDependenceGraphBuilder<DataDependenceGraph> {
347public:
349 const BasicBlockListType &BBs)
352 auto *RN = new RootDDGNode();
353 assert(RN && "Failed to allocate memory for DDG root node.");
354 Graph.addNode(*RN);
355 return *RN;
356 }
358 auto *SN = new SimpleDDGNode(I);
359 assert(SN && "Failed to allocate memory for simple DDG node.");
360 Graph.addNode(*SN);
361 return *SN;
362 }
364 auto *Pi = new PiBlockDDGNode(L);
365 assert(Pi && "Failed to allocate memory for pi-block node.");
366 Graph.addNode(*Pi);
367 return *Pi;
368 }
371 assert(E && "Failed to allocate memory for edge");
372 Graph.connect(Src, Tgt, *E);
373 return *E;
374 }
377 assert(E && "Failed to allocate memory for edge");
378 Graph.connect(Src, Tgt, *E);
379 return *E;
380 }
382 auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::Rooted);
383 assert(E && "Failed to allocate memory for edge");
384 assert(isa<RootDDGNode>(Src) && "Expected root node");
385 Graph.connect(Src, Tgt, *E);
386 return *E;
387 }
388
390 auto *PiNode = dyn_cast<const PiBlockDDGNode>(&N);
391 assert(PiNode && "Expected a pi-block node.");
392 return PiNode->getNodes();
393 }
394
395 /// Return true if the two nodes \pSrc and \pTgt are both simple nodes and
396 /// the consecutive instructions after merging belong to the same basic block.
397 bool areNodesMergeable(const DDGNode &Src, const DDGNode &Tgt) const final;
398 void mergeNodes(DDGNode &Src, DDGNode &Tgt) final;
399 bool shouldSimplify() const final;
400 bool shouldCreatePiBlocks() const final;
401};
402
403raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N);
404raw_ostream &operator<<(raw_ostream &OS, const DDGNode::NodeKind K);
405raw_ostream &operator<<(raw_ostream &OS, const DDGEdge &E);
406raw_ostream &operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K);
408
409//===--------------------------------------------------------------------===//
410// DDG Analysis Passes
411//===--------------------------------------------------------------------===//
412
413/// Analysis pass that builds the DDG for a loop.
415public:
416 using Result = std::unique_ptr<DataDependenceGraph>;
418
419private:
421 static AnalysisKey Key;
422};
423
424/// Textual printer pass for the DDG of a loop.
425class DDGAnalysisPrinterPass : public PassInfoMixin<DDGAnalysisPrinterPass> {
426public:
427 explicit DDGAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
430
431private:
432 raw_ostream &OS;
433};
434
435//===--------------------------------------------------------------------===//
436// DependenceGraphInfo Implementation
437//===--------------------------------------------------------------------===//
438
439template <typename NodeType>
441 const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const {
442 assert(Deps.empty() && "Expected empty output list at the start.");
443
444 // List of memory access instructions from src and dst nodes.
445 SmallVector<Instruction *, 8> SrcIList, DstIList;
446 auto isMemoryAccess = [](const Instruction *I) {
447 return I->mayReadOrWriteMemory();
448 };
449 Src.collectInstructions(isMemoryAccess, SrcIList);
450 Dst.collectInstructions(isMemoryAccess, DstIList);
451
452 for (auto *SrcI : SrcIList)
453 for (auto *DstI : DstIList)
454 if (auto Dep =
455 const_cast<DependenceInfo *>(&DI)->depends(SrcI, DstI, true))
456 Deps.push_back(std::move(Dep));
457
458 return !Deps.empty();
459}
460
461template <typename NodeType>
462std::string
464 const NodeType &Dst) const {
465 std::string Str;
466 raw_string_ostream OS(Str);
467 DependenceList Deps;
468 if (!getDependencies(Src, Dst, Deps))
469 return OS.str();
470 interleaveComma(Deps, OS, [&](const std::unique_ptr<Dependence> &D) {
471 D->dump(OS);
472 // Remove the extra new-line character printed by the dump
473 // method
474 if (OS.str().back() == '\n')
475 OS.str().pop_back();
476 });
477
478 return OS.str();
479}
480
481//===--------------------------------------------------------------------===//
482// GraphTraits specializations for the DDG
483//===--------------------------------------------------------------------===//
484
485/// non-const versions of the grapth trait specializations for DDG
486template <> struct GraphTraits<DDGNode *> {
487 using NodeRef = DDGNode *;
488
490 return &P->getTargetNode();
491 }
492
493 // Provide a mapped iterator so that the GraphTrait-based implementations can
494 // find the target nodes without having to explicitly go through the edges.
496 mapped_iterator<DDGNode::iterator, decltype(&DDGGetTargetNode)>;
498
499 static NodeRef getEntryNode(NodeRef N) { return N; }
501 return ChildIteratorType(N->begin(), &DDGGetTargetNode);
502 }
504 return ChildIteratorType(N->end(), &DDGGetTargetNode);
505 }
506
508 return N->begin();
509 }
510 static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
511};
512
513template <>
517 return &DG->getRoot();
518 }
520 return DG->begin();
521 }
522 static nodes_iterator nodes_end(DataDependenceGraph *DG) { return DG->end(); }
523};
524
525/// const versions of the grapth trait specializations for DDG
526template <> struct GraphTraits<const DDGNode *> {
527 using NodeRef = const DDGNode *;
528
530 return &P->getTargetNode();
531 }
532
533 // Provide a mapped iterator so that the GraphTrait-based implementations can
534 // find the target nodes without having to explicitly go through the edges.
536 mapped_iterator<DDGNode::const_iterator, decltype(&DDGGetTargetNode)>;
538
539 static NodeRef getEntryNode(NodeRef N) { return N; }
541 return ChildIteratorType(N->begin(), &DDGGetTargetNode);
542 }
544 return ChildIteratorType(N->end(), &DDGGetTargetNode);
545 }
546
548 return N->begin();
549 }
550 static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
551};
552
553template <>
558 return &DG->getRoot();
559 }
561 return DG->begin();
562 }
564 return DG->end();
565 }
566};
567
568} // namespace llvm
569
570#endif // LLVM_ANALYSIS_DDG_H
aarch64 promote const
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
SmallVector< Instruction *, 2 > InstructionListType
This file defines the interface and a base class implementation for a directed graph.
This header provides classes for managing per-loop analyses.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This abstract builder class defines a set of high-level steps for creating DDG-like graphs.
DependenceInfo & DI
Dependence information used to create memory dependence edges in the graph.
DataDependenceGraph & Graph
Reference to the graph that gets built by a concrete implementation of this builder.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
Textual printer pass for the DDG of a loop.
Definition: DDG.h:425
DDGAnalysisPrinterPass(raw_ostream &OS)
Definition: DDG.h:427
Analysis pass that builds the DDG for a loop.
Definition: DDG.h:414
std::unique_ptr< DataDependenceGraph > Result
Definition: DDG.h:416
Concrete implementation of a pure data dependence graph builder.
Definition: DDG.h:346
bool areNodesMergeable(const DDGNode &Src, const DDGNode &Tgt) const final
Return true if the two nodes \pSrc and \pTgt are both simple nodes and the consecutive instructions a...
Definition: DDG.cpp:266
DDGNode & createPiBlock(const NodeListType &L) final
Create a pi-block node in the graph representing a group of nodes in an SCC of the graph.
Definition: DDG.h:363
DDGNode & createFineGrainedNode(Instruction &I) final
Create an atomic node in the graph given a single instruction.
Definition: DDG.h:357
DDGBuilder(DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs)
Definition: DDG.h:348
bool shouldCreatePiBlocks() const final
Return true if creation of pi-blocks are supported and desired, and false otherwise.
Definition: DDG.cpp:301
DDGEdge & createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final
Definition: DDG.h:375
DDGEdge & createRootedEdge(DDGNode &Src, DDGNode &Tgt) final
Definition: DDG.h:381
DDGNode & createRootNode() final
Create the root node of the graph.
Definition: DDG.h:351
const NodeListType & getNodesInPiBlock(const DDGNode &N) final
Definition: DDG.h:389
DDGEdge & createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final
Definition: DDG.h:369
bool shouldSimplify() const final
Return true if graph simplification step is requested, and false otherwise.
Definition: DDG.cpp:299
void mergeNodes(DDGNode &Src, DDGNode &Tgt) final
Definition: DDG.cpp:279
Data Dependency Graph Edge.
Definition: DDG.h:213
DDGEdge & operator=(DDGEdge &&E)
Definition: DDG.h:230
bool isDefUse() const
Return true if this is a def-use edge, and false otherwise.
Definition: DDG.h:240
bool isRooted() const
Return true if this is an edge stemming from the root node, and false otherwise.
Definition: DDG.h:247
EdgeKind getKind() const
Get the edge kind.
Definition: DDG.h:237
EdgeKind
The kind of edge in the DDG.
Definition: DDG.h:216
DDGEdge(DDGEdge &&E)
Definition: DDG.h:227
bool isMemoryDependence() const
Return true if this is a memory dependence edge, and false otherwise.
Definition: DDG.h:243
DDGEdge(const DDGEdge &E)
Definition: DDG.h:226
DDGEdge(DDGNode &N, EdgeKind K)
Definition: DDG.h:225
DDGEdge(DDGNode &N)=delete
DDGEdge & operator=(const DDGEdge &E)=default
Data Dependence Graph Node The graph can represent the following types of nodes:
Definition: DDG.h:44
DDGNode & operator=(DDGNode &&N)
Definition: DDG.h:68
DDGNode(const DDGNode &N)=default
DDGNode(DDGNode &&N)
Definition: DDG.h:59
NodeKind getKind() const
Getter for the kind of this node.
Definition: DDG.h:75
DDGNode(const NodeKind K)
Definition: DDG.h:57
void setKind(NodeKind K)
Setter for the kind of this node.
Definition: DDG.h:85
DDGNode()=delete
virtual ~DDGNode()=0
DDGNode & operator=(const DDGNode &N)
Definition: DDG.h:62
bool collectInstructions(llvm::function_ref< bool(Instruction *)> const &Pred, InstructionListType &IList) const
Collect a list of instructions, in IList, for which predicate Pred evaluates to true when iterating o...
Definition: DDG.cpp:38
Represent an edge in the directed graph.
Definition: DirectedGraph.h:28
DGEdge< NodeType, EdgeType > & operator=(const DGEdge< NodeType, EdgeType > &E)
Definition: DirectedGraph.h:35
Represent a node in the directed graph.
Definition: DirectedGraph.h:73
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &N)
Definition: DirectedGraph.h:86
typename EdgeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:77
typename EdgeListTy::iterator iterator
Definition: DirectedGraph.h:76
Data Dependency Graph.
Definition: DDG.h:306
const PiBlockDDGNode * getPiBlock(const NodeType &N) const
If node N belongs to a pi-block return a pointer to the pi-block, otherwise return null.
Definition: DDG.cpp:243
DataDependenceGraph(DataDependenceGraph &&G)
Definition: DDG.h:316
DataDependenceGraph(const DataDependenceGraph &G)=delete
bool addNode(NodeType &N)
Add node N to the graph, if it's not added yet, and keep track of the root node as well as pi-blocks ...
Definition: DDG.cpp:220
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Definition: DDG.h:255
std::string getDependenceString(const NodeType &Src, const NodeType &Dst) const
Return a string representing the type of dependence that the dependence analysis identified between t...
Definition: DDG.h:463
const DependenceInfo DI
Definition: DDG.h:296
NodeType & getRoot() const
Return the root node of the graph.
Definition: DDG.h:271
DependenceGraphInfo(DependenceGraphInfo &&G)
Definition: DDG.h:263
StringRef getName() const
Return the label that is used to name this graph.
Definition: DDG.h:268
SmallVector< std::unique_ptr< Dependence >, 1 > DependenceList
Definition: DDG.h:257
DependenceGraphInfo(const DependenceGraphInfo &G)=delete
DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
Definition: DDG.h:261
virtual ~DependenceGraphInfo()=default
NodeType * Root
Definition: DDG.h:300
bool getDependencies(const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const
Collect all the data dependency infos coming from any pair of memory accesses from Src to Dst,...
Definition: DDG.h:440
std::string Name
Definition: DDG.h:291
DependenceInfo - This class is the main dependence-analysis driver.
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
Directed graph.
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 ...
const_iterator begin() const
const_iterator end() const
typename NodeListTy::iterator iterator
typename NodeListTy::const_iterator const_iterator
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
Subclass of DDGNode representing a pi-block.
Definition: DDG.h:170
PiBlockDDGNode & operator=(PiBlockDDGNode &&N)
Definition: DDG.h:182
const PiNodeList & getNodes() const
Get the list of nodes in this pi-block.
Definition: DDG.h:189
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:199
PiBlockDDGNode & operator=(const PiBlockDDGNode &N)=default
SmallVector< DDGNode *, 4 > PiNodeList
Definition: DDG.h:172
PiNodeList & getNodes()
Definition: DDG.h:193
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
Subclass of DDGNode representing the root node of the graph.
Definition: DDG.h:93
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:101
RootDDGNode(const RootDDGNode &N)=delete
~RootDDGNode()=default
static bool classof(const RootDDGNode *N)
Definition: DDG.h:104
RootDDGNode(RootDDGNode &&N)
Definition: DDG.h:97
Subclass of DDGNode representing single or multi-instruction nodes.
Definition: DDG.h:108
Instruction * getFirstInstruction() const
Get the first/last instruction in the node.
Definition: DDG.h:137
SimpleDDGNode & operator=(const SimpleDDGNode &N)=default
const InstructionListType & getInstructions() const
Get the list of instructions in this node.
Definition: DDG.h:127
SimpleDDGNode & operator=(SimpleDDGNode &&N)
Definition: DDG.h:120
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:141
static bool classof(const SimpleDDGNode *N)
Definition: DDG.h:145
InstructionListType & getInstructions()
Definition: DDG.h:131
Instruction * getLastInstruction() const
Definition: DDG.h:138
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:642
std::string & str()
Returns the string's reference.
Definition: raw_ostream.h:660
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2014
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
Definition: STLExtras.h:2098
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1862
Definition: BitVector.h:851
#define N
Determine the kind of a node from its type.
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
DDGNode::iterator ChildEdgeIteratorType
Definition: DDG.h:497
static DDGNode * DDGGetTargetNode(DGEdge< DDGNode, DDGEdge > *P)
Definition: DDG.h:489
static ChildIteratorType child_end(NodeRef N)
Definition: DDG.h:503
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: DDG.h:507
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: DDG.h:510
static ChildIteratorType child_begin(NodeRef N)
Definition: DDG.h:500
static NodeRef getEntryNode(NodeRef N)
Definition: DDG.h:499
static nodes_iterator nodes_end(DataDependenceGraph *DG)
Definition: DDG.h:522
DataDependenceGraph::iterator nodes_iterator
Definition: DDG.h:515
static nodes_iterator nodes_begin(DataDependenceGraph *DG)
Definition: DDG.h:519
static NodeRef getEntryNode(DataDependenceGraph *DG)
Definition: DDG.h:516
static ChildIteratorType child_end(NodeRef N)
Definition: DDG.h:543
static const DDGNode * DDGGetTargetNode(const DGEdge< DDGNode, DDGEdge > *P)
Definition: DDG.h:529
DDGNode::const_iterator ChildEdgeIteratorType
Definition: DDG.h:537
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: DDG.h:550
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: DDG.h:547
static NodeRef getEntryNode(NodeRef N)
Definition: DDG.h:539
static ChildIteratorType child_begin(NodeRef N)
Definition: DDG.h:540
static nodes_iterator nodes_begin(const DataDependenceGraph *DG)
Definition: DDG.h:560
DataDependenceGraph::const_iterator nodes_iterator
Definition: DDG.h:556
static NodeRef getEntryNode(const DataDependenceGraph *DG)
Definition: DDG.h:557
static nodes_iterator nodes_end(const DataDependenceGraph *DG)
Definition: DDG.h:563
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371