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 23namespace llvm { 24class DDGNode; 25class DDGEdge; 26using DDGNodeBase = DGNode<DDGNode, DDGEdge>; 27using DDGEdgeBase = DGEdge<DDGNode, DDGEdge>; 28using DDGBase = DirectedGraph<DDGNode, DDGEdge>; 29class 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. 42class DDGNode : public DDGNodeBase { 43public: 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; 55 DDGNode(const NodeKind K) : DDGNodeBase(), Kind(K) {} 56 DDGNode(const DDGNode &N) : DDGNodeBase(N), Kind(N.Kind) {} 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. 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 81protected: 82 /// Setter for the kind of this node. 83 void setKind(NodeKind K) { Kind = K; } 84 85private: 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. 91class RootDDGNode : public DDGNode { 92public: 93 RootDDGNode() : DDGNode(NodeKind::Root) {} 94 RootDDGNode(const RootDDGNode &N) = delete; 95 RootDDGNode(RootDDGNode &&N) : DDGNode(std::move(N)) {} 96 ~RootDDGNode() {} 97 98 /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc. 99 static bool classof(const DDGNode *N) { 100 return N->getKind() == NodeKind::Root; 101 } 102 static bool classof(const RootDDGNode *N) { return true; } 103}; 104 105/// Subclass of DDGNode representing single or multi-instruction nodes. 106class SimpleDDGNode : public DDGNode { 107 friend class DDGBuilder; 108 109public: 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. 129 const InstructionListType &getInstructions() const { 130 assert(!InstList.empty() && "Instruction List is empty."); 131 return InstList; 132 } 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. 139 Instruction *getFirstInstruction() const { return getInstructions().front(); } 140 Instruction *getLastInstruction() const { return getInstructions().back(); } 141 142 /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc. 143 static bool classof(const DDGNode *N) { 144 return N->getKind() == NodeKind::SingleInstruction || 145 N->getKind() == NodeKind::MultiInstruction; 146 } 147 static bool classof(const SimpleDDGNode *N) { return true; } 148 149private: 150 /// Append the list of instructions in \p Input to this node. 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 } 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} 172class PiBlockDDGNode : public DDGNode { 173public: 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. 195 const PiNodeList &getNodes() const { 196 assert(!NodeList.empty() && "Node list is empty."); 197 return NodeList; 198 } 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. 205 static bool classof(const DDGNode *N) { 206 return N->getKind() == NodeKind::PiBlock; 207 } 208 209private: 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. 219class DDGEdge : public DDGEdgeBase { 220public: 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; 231 DDGEdge(DDGNode &N, EdgeKind K) : DDGEdgeBase(N), Kind(K) {} 232 DDGEdge(const DDGEdge &E) : DDGEdgeBase(E), Kind(E.getKind()) {} 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 247 EdgeKind getKind() const { return Kind; }; 248 249 /// Return true if this is a def-use edge, and false otherwise. 250 bool isDefUse() const { return Kind == EdgeKind::RegisterDefUse; } 251 252 /// Return true if this is a memory dependence edge, and false otherwise. 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. 257 bool isRooted() const { return Kind == EdgeKind::Rooted; } 258 259private: 260 EdgeKind Kind; 261}; 262 263/// Encapsulate some common data and functionality needed for different 264/// variations of data dependence graphs. 265template <typename NodeType> class DependenceGraphInfo { 266public: 267 using DependenceList = SmallVector<std::unique_ptr<Dependence>, 1>; 268 269 DependenceGraphInfo() = delete; 270 DependenceGraphInfo(const DependenceGraphInfo &G) = delete; 271 DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo) 272 : Name(N), DI(DepInfo), Root(nullptr) {} 273 DependenceGraphInfo(DependenceGraphInfo &&G) 274 : Name(std::move(G.Name)), DI(std::move(G.DI)), Root(G.Root) {} 275 virtual ~DependenceGraphInfo() {} 276 277 /// Return the label that is used to name this graph. 278 StringRef getName() const { return Name; } 279 280 /// Return the root node of the graph. 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 299protected: 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 313using DDGInfo = DependenceGraphInfo<DDGNode>; 314 315/// Data Dependency Graph 316class DataDependenceGraph : public DDGBase, public DDGInfo { 317 friend AbstractDependenceGraphBuilder<DataDependenceGraph>; 318 friend class DDGBuilder; 319 320public: 321 using NodeType = DDGNode; 322 using EdgeType = DDGEdge; 323 324 DataDependenceGraph() = delete; 325 DataDependenceGraph(const DataDependenceGraph &G) = delete; 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 336protected: 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 342private: 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. 356class DDGBuilder : public AbstractDependenceGraphBuilder<DataDependenceGraph> { 357public: 358 DDGBuilder(DataDependenceGraph &G, DependenceInfo &D, 359 const BasicBlockListType &BBs) 360 : AbstractDependenceGraphBuilder(G, D, BBs) {} 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 } 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 } 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 } 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 } 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 } 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 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 414raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N); 415raw_ostream &operator<<(raw_ostream &OS, const DDGNode::NodeKind K); 416raw_ostream &operator<<(raw_ostream &OS, const DDGEdge &E); 417raw_ostream &operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K); 418raw_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. 425class DDGAnalysis : public AnalysisInfoMixin<DDGAnalysis> { 426public: 427 using Result = std::unique_ptr<DataDependenceGraph>; 428 Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR); 429 430private: 431 friend AnalysisInfoMixin<DDGAnalysis>; 432 static AnalysisKey Key; 433}; 434 435/// Textual printer pass for the DDG of a loop. 436class DDGAnalysisPrinterPass : public PassInfoMixin<DDGAnalysisPrinterPass> { 437public: 438 explicit DDGAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {} 439 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 440 LoopStandardAnalysisResults &AR, LPMUpdater &U); 441 442private: 443 raw_ostream &OS; 444}; 445 446//===--------------------------------------------------------------------===// 447// DependenceGraphInfo Implementation 448//===--------------------------------------------------------------------===// 449 450template <typename NodeType> 451bool 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 472template <typename NodeType> 473std::string 474DependenceGraphInfo<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 497template <> 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 524template <> 525struct 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 537template <> 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 564template <> 565struct 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