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=(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=(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(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} 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=(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=(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(*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(*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(*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, Tgt, *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, Tgt, *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, Tgt, *E); 386 return *E; 387 } 388 389 const NodeListType &getNodesInPiBlock(const DDGNode &N) final { 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 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 431 private: 432 raw_ostream &OS; 433 }; 434 435 //===--------------------------------------------------------------------===// 436 // DependenceGraphInfo Implementation 437 //===--------------------------------------------------------------------===// 438 439 template <typename NodeType> 440 bool DependenceGraphInfo<NodeType>::getDependencies( 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 461 template <typename NodeType> 462 std::string 463 DependenceGraphInfo<NodeType>::getDependenceString(const NodeType &Src, 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 486 template <> struct GraphTraits<DDGNode *> { 487 using NodeRef = DDGNode *; 488 489 static DDGNode *DDGGetTargetNode(DGEdge<DDGNode, DDGEdge> *P) { 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. 495 using ChildIteratorType = 496 mapped_iterator<DDGNode::iterator, decltype(&DDGGetTargetNode)>; 497 using ChildEdgeIteratorType = DDGNode::iterator; 498 499 static NodeRef getEntryNode(NodeRef N) { return N; } 500 static ChildIteratorType child_begin(NodeRef N) { 501 return ChildIteratorType(N->begin(), &DDGGetTargetNode); 502 } 503 static ChildIteratorType child_end(NodeRef N) { 504 return ChildIteratorType(N->end(), &DDGGetTargetNode); 505 } 506 507 static ChildEdgeIteratorType child_edge_begin(NodeRef N) { 508 return N->begin(); 509 } 510 static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); } 511 }; 512 513 template <> 514 struct GraphTraits<DataDependenceGraph *> : public GraphTraits<DDGNode *> { 515 using nodes_iterator = DataDependenceGraph::iterator; 516 static NodeRef getEntryNode(DataDependenceGraph *DG) { 517 return &DG->getRoot(); 518 } 519 static nodes_iterator nodes_begin(DataDependenceGraph *DG) { 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 526 template <> struct GraphTraits<const DDGNode *> { 527 using NodeRef = const DDGNode *; 528 529 static const DDGNode *DDGGetTargetNode(const DGEdge<DDGNode, DDGEdge> *P) { 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. 535 using ChildIteratorType = 536 mapped_iterator<DDGNode::const_iterator, decltype(&DDGGetTargetNode)>; 537 using ChildEdgeIteratorType = DDGNode::const_iterator; 538 539 static NodeRef getEntryNode(NodeRef N) { return N; } 540 static ChildIteratorType child_begin(NodeRef N) { 541 return ChildIteratorType(N->begin(), &DDGGetTargetNode); 542 } 543 static ChildIteratorType child_end(NodeRef N) { 544 return ChildIteratorType(N->end(), &DDGGetTargetNode); 545 } 546 547 static ChildEdgeIteratorType child_edge_begin(NodeRef N) { 548 return N->begin(); 549 } 550 static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); } 551 }; 552 553 template <> 554 struct GraphTraits<const DataDependenceGraph *> 555 : public GraphTraits<const DDGNode *> { 556 using nodes_iterator = DataDependenceGraph::const_iterator; 557 static NodeRef getEntryNode(const DataDependenceGraph *DG) { 558 return &DG->getRoot(); 559 } 560 static nodes_iterator nodes_begin(const DataDependenceGraph *DG) { 561 return DG->begin(); 562 } 563 static nodes_iterator nodes_end(const DataDependenceGraph *DG) { 564 return DG->end(); 565 } 566 }; 567 568 } // namespace llvm 569 570 #endif // LLVM_ANALYSIS_DDG_H 571