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 | |
22 | namespace llvm { |
23 | class Function; |
24 | class Loop; |
25 | class LoopInfo; |
26 | class DDGNode; |
27 | class DDGEdge; |
28 | using DDGNodeBase = DGNode<DDGNode, DDGEdge>; |
29 | using DDGEdgeBase = DGEdge<DDGNode, DDGEdge>; |
30 | using DDGBase = DirectedGraph<DDGNode, DDGEdge>; |
31 | class 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. |
44 | class DDGNode : public DDGNodeBase { |
45 | public: |
46 | using InstructionListType = SmallVectorImpl<Instruction *>; |
47 | |
48 | enum class NodeKind { |
49 | Unknown, |
50 | SingleInstruction, |
51 | MultiInstruction, |
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 | |
62 | DDGNode &operator=(const DDGNode &N) { |
63 | DGNode::operator=(N); |
64 | Kind = N.Kind; |
65 | return *this; |
66 | } |
67 | |
68 | DDGNode &operator=(DDGNode &&N) { |
69 | DGNode::operator=(N: 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 | |
83 | protected: |
84 | /// Setter for the kind of this node. |
85 | void setKind(NodeKind K) { Kind = K; } |
86 | |
87 | private: |
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. |
93 | class RootDDGNode : public DDGNode { |
94 | public: |
95 | RootDDGNode() : DDGNode(NodeKind::Root) {} |
96 | RootDDGNode(const RootDDGNode &N) = delete; |
97 | RootDDGNode(RootDDGNode &&N) : DDGNode(std::move(N)) {} |
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. |
108 | class SimpleDDGNode : public DDGNode { |
109 | friend class DDGBuilder; |
110 | |
111 | public: |
112 | SimpleDDGNode() = delete; |
113 | SimpleDDGNode(Instruction &I); |
114 | SimpleDDGNode(const SimpleDDGNode &N); |
115 | SimpleDDGNode(SimpleDDGNode &&N); |
116 | ~SimpleDDGNode(); |
117 | |
118 | SimpleDDGNode &operator=(const SimpleDDGNode &N) = default; |
119 | |
120 | SimpleDDGNode &operator=(SimpleDDGNode &&N) { |
121 | DDGNode::operator=(N: std::move(N)); |
122 | InstList = std::move(N.InstList); |
123 | return *this; |
124 | } |
125 | |
126 | /// Get the list of instructions in this node. |
127 | const InstructionListType &getInstructions() const { |
128 | assert(!InstList.empty() && "Instruction List is empty." ); |
129 | return InstList; |
130 | } |
131 | InstructionListType &getInstructions() { |
132 | return const_cast<InstructionListType &>( |
133 | static_cast<const SimpleDDGNode *>(this)->getInstructions()); |
134 | } |
135 | |
136 | /// Get the first/last instruction in the node. |
137 | Instruction *getFirstInstruction() const { return getInstructions().front(); } |
138 | Instruction *getLastInstruction() const { return getInstructions().back(); } |
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 | |
147 | private: |
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) |
151 | ? NodeKind::SingleInstruction |
152 | : NodeKind::MultiInstruction); |
153 | llvm::append_range(C&: InstList, R: Input); |
154 | } |
155 | void appendInstructions(const SimpleDDGNode &Input) { |
156 | appendInstructions(Input: 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} |
170 | class PiBlockDDGNode : public DDGNode { |
171 | public: |
172 | using PiNodeList = SmallVector<DDGNode *, 4>; |
173 | |
174 | PiBlockDDGNode() = delete; |
175 | PiBlockDDGNode(const PiNodeList &List); |
176 | PiBlockDDGNode(const PiBlockDDGNode &N); |
177 | PiBlockDDGNode(PiBlockDDGNode &&N); |
178 | ~PiBlockDDGNode(); |
179 | |
180 | PiBlockDDGNode &operator=(const PiBlockDDGNode &N) = default; |
181 | |
182 | PiBlockDDGNode &operator=(PiBlockDDGNode &&N) { |
183 | DDGNode::operator=(N: 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 | } |
193 | PiNodeList &getNodes() { |
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 | |
203 | private: |
204 | /// List of nodes in this pi-block. |
205 | PiNodeList NodeList; |
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. |
213 | class DDGEdge : public DDGEdgeBase { |
214 | public: |
215 | /// The kind of edge in the DDG |
216 | enum class EdgeKind { |
217 | Unknown, |
218 | RegisterDefUse, |
219 | MemoryDependence, |
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 | |
230 | DDGEdge &operator=(DDGEdge &&E) { |
231 | DDGEdgeBase::operator=(E: 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 | |
249 | private: |
250 | EdgeKind Kind; |
251 | }; |
252 | |
253 | /// Encapsulate some common data and functionality needed for different |
254 | /// variations of data dependence graphs. |
255 | template <typename NodeType> class DependenceGraphInfo { |
256 | public: |
257 | using DependenceList = SmallVector<std::unique_ptr<Dependence>, 1>; |
258 | |
259 | DependenceGraphInfo() = delete; |
260 | DependenceGraphInfo(const DependenceGraphInfo &G) = delete; |
261 | DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo) |
262 | : Name(N), DI(DepInfo), Root(nullptr) {} |
263 | DependenceGraphInfo(DependenceGraphInfo &&G) |
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 | |
289 | protected: |
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. |
296 | const DependenceInfo 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 | |
303 | using DDGInfo = DependenceGraphInfo<DDGNode>; |
304 | |
305 | /// Data Dependency Graph |
306 | class DataDependenceGraph : public DDGBase, public DDGInfo { |
307 | friend AbstractDependenceGraphBuilder<DataDependenceGraph>; |
308 | friend class DDGBuilder; |
309 | |
310 | public: |
311 | using NodeType = DDGNode; |
312 | using EdgeType = DDGEdge; |
313 | |
314 | DataDependenceGraph() = delete; |
315 | DataDependenceGraph(const DataDependenceGraph &G) = delete; |
316 | DataDependenceGraph(DataDependenceGraph &&G) |
317 | : DDGBase(std::move(G)), DDGInfo(std::move(G)) {} |
318 | DataDependenceGraph(Function &F, DependenceInfo &DI); |
319 | DataDependenceGraph(Loop &L, LoopInfo &LI, DependenceInfo &DI); |
320 | ~DataDependenceGraph(); |
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 | |
326 | protected: |
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 | |
332 | private: |
333 | using PiBlockMapType = DenseMap<const NodeType *, const PiBlockDDGNode *>; |
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. |
346 | class DDGBuilder : public AbstractDependenceGraphBuilder<DataDependenceGraph> { |
347 | public: |
348 | DDGBuilder(DataDependenceGraph &G, DependenceInfo &D, |
349 | const BasicBlockListType &BBs) |
350 | : AbstractDependenceGraphBuilder(G, D, BBs) {} |
351 | DDGNode &createRootNode() final { |
352 | auto *RN = new RootDDGNode(); |
353 | assert(RN && "Failed to allocate memory for DDG root node." ); |
354 | Graph.addNode(N&: *RN); |
355 | return *RN; |
356 | } |
357 | DDGNode &createFineGrainedNode(Instruction &I) final { |
358 | auto *SN = new SimpleDDGNode(I); |
359 | assert(SN && "Failed to allocate memory for simple DDG node." ); |
360 | Graph.addNode(N&: *SN); |
361 | return *SN; |
362 | } |
363 | DDGNode &createPiBlock(const NodeListType &L) final { |
364 | auto *Pi = new PiBlockDDGNode(L); |
365 | assert(Pi && "Failed to allocate memory for pi-block node." ); |
366 | Graph.addNode(N&: *Pi); |
367 | return *Pi; |
368 | } |
369 | DDGEdge &createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final { |
370 | auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::RegisterDefUse); |
371 | assert(E && "Failed to allocate memory for edge" ); |
372 | Graph.connect(Src, Dst&: Tgt, E&: *E); |
373 | return *E; |
374 | } |
375 | DDGEdge &createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final { |
376 | auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::MemoryDependence); |
377 | assert(E && "Failed to allocate memory for edge" ); |
378 | Graph.connect(Src, Dst&: Tgt, E&: *E); |
379 | return *E; |
380 | } |
381 | DDGEdge &createRootedEdge(DDGNode &Src, DDGNode &Tgt) final { |
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, Dst&: Tgt, E&: *E); |
386 | return *E; |
387 | } |
388 | |
389 | const NodeListType &getNodesInPiBlock(const DDGNode &N) final { |
390 | auto *PiNode = dyn_cast<const PiBlockDDGNode>(Val: &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 | |
403 | raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N); |
404 | raw_ostream &operator<<(raw_ostream &OS, const DDGNode::NodeKind K); |
405 | raw_ostream &operator<<(raw_ostream &OS, const DDGEdge &E); |
406 | raw_ostream &operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K); |
407 | raw_ostream &operator<<(raw_ostream &OS, const DataDependenceGraph &G); |
408 | |
409 | //===--------------------------------------------------------------------===// |
410 | // DDG Analysis Passes |
411 | //===--------------------------------------------------------------------===// |
412 | |
413 | /// Analysis pass that builds the DDG for a loop. |
414 | class DDGAnalysis : public AnalysisInfoMixin<DDGAnalysis> { |
415 | public: |
416 | using Result = std::unique_ptr<DataDependenceGraph>; |
417 | Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR); |
418 | |
419 | private: |
420 | friend AnalysisInfoMixin<DDGAnalysis>; |
421 | static AnalysisKey Key; |
422 | }; |
423 | |
424 | /// Textual printer pass for the DDG of a loop. |
425 | class DDGAnalysisPrinterPass : public PassInfoMixin<DDGAnalysisPrinterPass> { |
426 | public: |
427 | explicit DDGAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {} |
428 | PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, |
429 | LoopStandardAnalysisResults &AR, LPMUpdater &U); |
430 | static bool isRequired() { return true; } |
431 | |
432 | private: |
433 | raw_ostream &OS; |
434 | }; |
435 | |
436 | //===--------------------------------------------------------------------===// |
437 | // DependenceGraphInfo Implementation |
438 | //===--------------------------------------------------------------------===// |
439 | |
440 | template <typename NodeType> |
441 | bool DependenceGraphInfo<NodeType>::getDependencies( |
442 | const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const { |
443 | assert(Deps.empty() && "Expected empty output list at the start." ); |
444 | |
445 | // List of memory access instructions from src and dst nodes. |
446 | SmallVector<Instruction *, 8> SrcIList, DstIList; |
447 | auto isMemoryAccess = [](const Instruction *I) { |
448 | return I->mayReadOrWriteMemory(); |
449 | }; |
450 | Src.collectInstructions(isMemoryAccess, SrcIList); |
451 | Dst.collectInstructions(isMemoryAccess, DstIList); |
452 | |
453 | for (auto *SrcI : SrcIList) |
454 | for (auto *DstI : DstIList) |
455 | if (auto Dep = |
456 | const_cast<DependenceInfo *>(&DI)->depends(Src: SrcI, Dst: DstI, PossiblyLoopIndependent: true)) |
457 | Deps.push_back(Elt: std::move(Dep)); |
458 | |
459 | return !Deps.empty(); |
460 | } |
461 | |
462 | template <typename NodeType> |
463 | std::string |
464 | DependenceGraphInfo<NodeType>::getDependenceString(const NodeType &Src, |
465 | const NodeType &Dst) const { |
466 | std::string Str; |
467 | raw_string_ostream OS(Str); |
468 | DependenceList Deps; |
469 | if (!getDependencies(Src, Dst, Deps)) |
470 | return OS.str(); |
471 | interleaveComma(Deps, OS, [&](const std::unique_ptr<Dependence> &D) { |
472 | D->dump(OS); |
473 | // Remove the extra new-line character printed by the dump |
474 | // method |
475 | if (OS.str().back() == '\n') |
476 | OS.str().pop_back(); |
477 | }); |
478 | |
479 | return OS.str(); |
480 | } |
481 | |
482 | //===--------------------------------------------------------------------===// |
483 | // GraphTraits specializations for the DDG |
484 | //===--------------------------------------------------------------------===// |
485 | |
486 | /// non-const versions of the grapth trait specializations for DDG |
487 | template <> struct GraphTraits<DDGNode *> { |
488 | using NodeRef = DDGNode *; |
489 | |
490 | static DDGNode *DDGGetTargetNode(DGEdge<DDGNode, DDGEdge> *P) { |
491 | return &P->getTargetNode(); |
492 | } |
493 | |
494 | // Provide a mapped iterator so that the GraphTrait-based implementations can |
495 | // find the target nodes without having to explicitly go through the edges. |
496 | using ChildIteratorType = |
497 | mapped_iterator<DDGNode::iterator, decltype(&DDGGetTargetNode)>; |
498 | using ChildEdgeIteratorType = DDGNode::iterator; |
499 | |
500 | static NodeRef getEntryNode(NodeRef N) { return N; } |
501 | static ChildIteratorType child_begin(NodeRef N) { |
502 | return ChildIteratorType(N->begin(), &DDGGetTargetNode); |
503 | } |
504 | static ChildIteratorType child_end(NodeRef N) { |
505 | return ChildIteratorType(N->end(), &DDGGetTargetNode); |
506 | } |
507 | |
508 | static ChildEdgeIteratorType child_edge_begin(NodeRef N) { |
509 | return N->begin(); |
510 | } |
511 | static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); } |
512 | }; |
513 | |
514 | template <> |
515 | struct GraphTraits<DataDependenceGraph *> : public GraphTraits<DDGNode *> { |
516 | using nodes_iterator = DataDependenceGraph::iterator; |
517 | static NodeRef getEntryNode(DataDependenceGraph *DG) { |
518 | return &DG->getRoot(); |
519 | } |
520 | static nodes_iterator nodes_begin(DataDependenceGraph *DG) { |
521 | return DG->begin(); |
522 | } |
523 | static nodes_iterator nodes_end(DataDependenceGraph *DG) { return DG->end(); } |
524 | }; |
525 | |
526 | /// const versions of the grapth trait specializations for DDG |
527 | template <> struct GraphTraits<const DDGNode *> { |
528 | using NodeRef = const DDGNode *; |
529 | |
530 | static const DDGNode *DDGGetTargetNode(const DGEdge<DDGNode, DDGEdge> *P) { |
531 | return &P->getTargetNode(); |
532 | } |
533 | |
534 | // Provide a mapped iterator so that the GraphTrait-based implementations can |
535 | // find the target nodes without having to explicitly go through the edges. |
536 | using ChildIteratorType = |
537 | mapped_iterator<DDGNode::const_iterator, decltype(&DDGGetTargetNode)>; |
538 | using ChildEdgeIteratorType = DDGNode::const_iterator; |
539 | |
540 | static NodeRef getEntryNode(NodeRef N) { return N; } |
541 | static ChildIteratorType child_begin(NodeRef N) { |
542 | return ChildIteratorType(N->begin(), &DDGGetTargetNode); |
543 | } |
544 | static ChildIteratorType child_end(NodeRef N) { |
545 | return ChildIteratorType(N->end(), &DDGGetTargetNode); |
546 | } |
547 | |
548 | static ChildEdgeIteratorType child_edge_begin(NodeRef N) { |
549 | return N->begin(); |
550 | } |
551 | static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); } |
552 | }; |
553 | |
554 | template <> |
555 | struct GraphTraits<const DataDependenceGraph *> |
556 | : public GraphTraits<const DDGNode *> { |
557 | using nodes_iterator = DataDependenceGraph::const_iterator; |
558 | static NodeRef getEntryNode(const DataDependenceGraph *DG) { |
559 | return &DG->getRoot(); |
560 | } |
561 | static nodes_iterator nodes_begin(const DataDependenceGraph *DG) { |
562 | return DG->begin(); |
563 | } |
564 | static nodes_iterator nodes_end(const DataDependenceGraph *DG) { |
565 | return DG->end(); |
566 | } |
567 | }; |
568 | |
569 | } // namespace llvm |
570 | |
571 | #endif // LLVM_ANALYSIS_DDG_H |
572 | |