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