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