include/llvm/Analysis/DDG.h

   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/DirectedGraph.h"
  17 #include "llvm/Analysis/DependenceAnalysis.h"
  18 #include "llvm/Analysis/DependenceGraphBuilder.h"
  19 #include "llvm/Analysis/LoopAnalysisManager.h"
  20 #include "llvm/IR/Instructions.h"
  21 #include <unordered_map>
  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. Root node is a special node that connects to all components such that
  37 ///    there is always a path from it to any node in the graph.
  38 class DDGNode : public DDGNodeBase {
  39 public:
  40   using InstructionListType = SmallVectorImpl<Instruction *>;
  41
  42   enum class NodeKind {
  43     Unknown,
  44     SingleInstruction,
  45     MultiInstruction,
  46     Root,
  47   };
  48
  49   DDGNode() = delete;
  50   DDGNode(const NodeKind K) : DDGNodeBase(), Kind(K) {}
  51   DDGNode(const DDGNode &N) : DDGNodeBase(N), Kind(N.Kind) {}
  52   DDGNode(DDGNode &&N) : DDGNodeBase(std::move(N)), Kind(N.Kind) {}
  53   virtual ~DDGNode() = 0;
  54
  55   DDGNode &operator=(const DDGNode &N) {
  56     DGNode::operator=(N);
  57     Kind = N.Kind;
  58     return *this;
  59   }
  60
  61   DDGNode &operator=(DDGNode &&N) {
  62     DGNode::operator=(std::move(N));
  63     Kind = N.Kind;
  64     return *this;
  65   }
  66
  67   /// Getter for the kind of this node.
  68   NodeKind getKind() const { return Kind; }
  69
  70   /// Collect a list of instructions, in \p IList, for which predicate \p Pred
  71   /// evaluates to true when iterating over instructions of this node. Return
  72   /// true if at least one instruction was collected, and false otherwise.
  73   bool collectInstructions(llvm::function_ref<bool(Instruction *)> const &Pred,
  74                            InstructionListType &IList) const;
  75
  76 protected:
  77   /// Setter for the kind of this node.
  78   void setKind(NodeKind K) { Kind = K; }
  79
  80 private:
  81   NodeKind Kind;
  82 };
  83
  84 /// Subclass of DDGNode representing the root node of the graph.
  85 /// There should only be one such node in a given graph.
  86 class RootDDGNode : public DDGNode {
  87 public:
  88   RootDDGNode() : DDGNode(NodeKind::Root) {}
  89   RootDDGNode(const RootDDGNode &N) = delete;
  90   RootDDGNode(RootDDGNode &&N) : DDGNode(std::move(N)) {}
  91   ~RootDDGNode() {}
  92
  93   /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
  94   static bool classof(const DDGNode *N) {
  95     return N->getKind() == NodeKind::Root;
  96   }
  97   static bool classof(const RootDDGNode *N) { return true; }
  98 };
  99
 100 /// Subclass of DDGNode representing single or multi-instruction nodes.
 101 class SimpleDDGNode : public DDGNode {
 102 public:
 103   SimpleDDGNode() = delete;
 104   SimpleDDGNode(Instruction &I);
 105   SimpleDDGNode(const SimpleDDGNode &N);
 106   SimpleDDGNode(SimpleDDGNode &&N);
 107   ~SimpleDDGNode();
 108
 109   SimpleDDGNode &operator=(const SimpleDDGNode &N) {
 110     DDGNode::operator=(N);
 111     InstList = N.InstList;
 112     return *this;
 113   }
 114
 115   SimpleDDGNode &operator=(SimpleDDGNode &&N) {
 116     DDGNode::operator=(std::move(N));
 117     InstList = std::move(N.InstList);
 118     return *this;
 119   }
 120
 121   /// Get the list of instructions in this node.
 122   const InstructionListType &getInstructions() const {
 123     assert(!InstList.empty() && "Instruction List is empty.");
 124     return InstList;
 125   }
 126   InstructionListType &getInstructions() {
 127     return const_cast<InstructionListType &>(
 128         static_cast<const SimpleDDGNode *>(this)->getInstructions());
 129   }
 130
 131   /// Get the first/last instruction in the node.
 132   Instruction *getFirstInstruction() const { return getInstructions().front(); }
 133   Instruction *getLastInstruction() const { return getInstructions().back(); }
 134
 135   /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
 136   static bool classof(const DDGNode *N) {
 137     return N->getKind() == NodeKind::SingleInstruction ||
 138            N->getKind() == NodeKind::MultiInstruction;
 139   }
 140   static bool classof(const SimpleDDGNode *N) { return true; }
 141
 142 private:
 143   /// Append the list of instructions in \p Input to this node.
 144   void appendInstructions(const InstructionListType &Input) {
 145     setKind((InstList.size() == 0 && Input.size() == 1)
 146                 ? NodeKind::SingleInstruction
 147                 : NodeKind::MultiInstruction);
 148     InstList.insert(InstList.end(), Input.begin(), Input.end());
 149   }
 150   void appendInstructions(const SimpleDDGNode &Input) {
 151     appendInstructions(Input.getInstructions());
 152   }
 153
 154   /// List of instructions associated with a single or multi-instruction node.
 155   SmallVector<Instruction *, 2> InstList;
 156 };
 157
 158 /// Data Dependency Graph Edge.
 159 /// An edge in the DDG can represent a def-use relationship or
 160 /// a memory dependence based on the result of DependenceAnalysis.
 161 /// A rooted edge connects the root node to one of the components
 162 /// of the graph.
 163 class DDGEdge : public DDGEdgeBase {
 164 public:
 165   /// The kind of edge in the DDG
 166   enum class EdgeKind { Unknown, RegisterDefUse, MemoryDependence, Rooted };
 167
 168   explicit DDGEdge(DDGNode &N) = delete;
 169   DDGEdge(DDGNode &N, EdgeKind K) : DDGEdgeBase(N), Kind(K) {}
 170   DDGEdge(const DDGEdge &E) : DDGEdgeBase(E), Kind(E.getKind()) {}
 171   DDGEdge(DDGEdge &&E) : DDGEdgeBase(std::move(E)), Kind(E.Kind) {}
 172   DDGEdge &operator=(const DDGEdge &E) {
 173     DDGEdgeBase::operator=(E);
 174     Kind = E.Kind;
 175     return *this;
 176   }
 177
 178   DDGEdge &operator=(DDGEdge &&E) {
 179     DDGEdgeBase::operator=(std::move(E));
 180     Kind = E.Kind;
 181     return *this;
 182   }
 183
 184   /// Get the edge kind
 185   EdgeKind getKind() const { return Kind; };
 186
 187   /// Return true if this is a def-use edge, and false otherwise.
 188   bool isDefUse() const { return Kind == EdgeKind::RegisterDefUse; }
 189
 190   /// Return true if this is a memory dependence edge, and false otherwise.
 191   bool isMemoryDependence() const { return Kind == EdgeKind::MemoryDependence; }
 192
 193   /// Return true if this is an edge stemming from the root node, and false
 194   /// otherwise.
 195   bool isRooted() const { return Kind == EdgeKind::Rooted; }
 196
 197 private:
 198   EdgeKind Kind;
 199 };
 200
 201 /// Encapsulate some common data and functionality needed for different
 202 /// variations of data dependence graphs.
 203 template <typename NodeType> class DependenceGraphInfo {
 204 public:
 205   using DependenceList = SmallVector<std::unique_ptr<Dependence>, 1>;
 206
 207   DependenceGraphInfo() = delete;
 208   DependenceGraphInfo(const DependenceGraphInfo &G) = delete;
 209   DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
 210       : Name(N), DI(DepInfo), Root(nullptr) {}
 211   DependenceGraphInfo(DependenceGraphInfo &&G)
 212       : Name(std::move(G.Name)), DI(std::move(G.DI)), Root(G.Root) {}
 213   virtual ~DependenceGraphInfo() {}
 214
 215   /// Return the label that is used to name this graph.
 216   const StringRef getName() const { return Name; }
 217
 218   /// Return the root node of the graph.
 219   NodeType &getRoot() const {
 220     assert(Root && "Root node is not available yet. Graph construction may "
 221                    "still be in progress\n");
 222     return *Root;
 223   }
 224
 225 protected:
 226   // Name of the graph.
 227   std::string Name;
 228
 229   // Store a copy of DependenceInfo in the graph, so that individual memory
 230   // dependencies don't need to be stored. Instead when the dependence is
 231   // queried it is recomputed using @DI.
 232   const DependenceInfo DI;
 233
 234   // A special node in the graph that has an edge to every connected component of
 235   // the graph, to ensure all nodes are reachable in a graph walk.
 236   NodeType *Root = nullptr;
 237 };
 238
 239 using DDGInfo = DependenceGraphInfo<DDGNode>;
 240
 241 /// Data Dependency Graph
 242 class DataDependenceGraph : public DDGBase, public DDGInfo {
 243   friend class DDGBuilder;
 244
 245 public:
 246   using NodeType = DDGNode;
 247   using EdgeType = DDGEdge;
 248
 249   DataDependenceGraph() = delete;
 250   DataDependenceGraph(const DataDependenceGraph &G) = delete;
 251   DataDependenceGraph(DataDependenceGraph &&G)
 252       : DDGBase(std::move(G)), DDGInfo(std::move(G)) {}
 253   DataDependenceGraph(Function &F, DependenceInfo &DI);
 254   DataDependenceGraph(const Loop &L, DependenceInfo &DI);
 255   ~DataDependenceGraph();
 256
 257 protected:
 258   /// Add node \p N to the graph, if it's not added yet, and keep track of
 259   /// the root node. Return true if node is successfully added.
 260   bool addNode(NodeType &N);
 261
 262 };
 263
 264 /// Concrete implementation of a pure data dependence graph builder. This class
 265 /// provides custom implementation for the pure-virtual functions used in the
 266 /// generic dependence graph build algorithm.
 267 ///
 268 /// For information about time complexity of the build algorithm see the
 269 /// comments near the declaration of AbstractDependenceGraphBuilder.
 270 class DDGBuilder : public AbstractDependenceGraphBuilder<DataDependenceGraph> {
 271 public:
 272   DDGBuilder(DataDependenceGraph &G, DependenceInfo &D,
 273              const BasicBlockListType &BBs)
 274       : AbstractDependenceGraphBuilder(G, D, BBs) {}
 275   DDGNode &createRootNode() final override {
 276     auto *RN = new RootDDGNode();
 277     assert(RN && "Failed to allocate memory for DDG root node.");
 278     Graph.addNode(*RN);
 279     return *RN;
 280   }
 281   DDGNode &createFineGrainedNode(Instruction &I) final override {
 282     auto *SN = new SimpleDDGNode(I);
 283     assert(SN && "Failed to allocate memory for simple DDG node.");
 284     Graph.addNode(*SN);
 285     return *SN;
 286   }
 287   DDGEdge &createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final override {
 288     auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::RegisterDefUse);
 289     assert(E && "Failed to allocate memory for edge");
 290     Graph.connect(Src, Tgt, *E);
 291     return *E;
 292   }
 293   DDGEdge &createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final override {
 294     auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::MemoryDependence);
 295     assert(E && "Failed to allocate memory for edge");
 296     Graph.connect(Src, Tgt, *E);
 297     return *E;
 298   }
 299   DDGEdge &createRootedEdge(DDGNode &Src, DDGNode &Tgt) final override {
 300     auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::Rooted);
 301     assert(E && "Failed to allocate memory for edge");
 302     assert(isa<RootDDGNode>(Src) && "Expected root node");
 303     Graph.connect(Src, Tgt, *E);
 304     return *E;
 305   }
 306
 307 };
 308
 309 raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N);
 310 raw_ostream &operator<<(raw_ostream &OS, const DDGNode::NodeKind K);
 311 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge &E);
 312 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K);
 313 raw_ostream &operator<<(raw_ostream &OS, const DataDependenceGraph &G);
 314
 315 //===--------------------------------------------------------------------===//
 316 // DDG Analysis Passes
 317 //===--------------------------------------------------------------------===//
 318
 319 /// Analysis pass that builds the DDG for a loop.
 320 class DDGAnalysis : public AnalysisInfoMixin<DDGAnalysis> {
 321 public:
 322   using Result = std::unique_ptr<DataDependenceGraph>;
 323   Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR);
 324
 325 private:
 326   friend AnalysisInfoMixin<DDGAnalysis>;
 327   static AnalysisKey Key;
 328 };
 329
 330 /// Textual printer pass for the DDG of a loop.
 331 class DDGAnalysisPrinterPass : public PassInfoMixin<DDGAnalysisPrinterPass> {
 332 public:
 333   explicit DDGAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
 334   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
 335                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
 336
 337 private:
 338   raw_ostream &OS;
 339 };
 340
 341 //===--------------------------------------------------------------------===//
 342 // GraphTraits specializations for the DDG
 343 //===--------------------------------------------------------------------===//
 344
 345 /// non-const versions of the grapth trait specializations for DDG
 346 template <> struct GraphTraits<DDGNode *> {
 347   using NodeRef = DDGNode *;
 348
 349   static DDGNode *DDGGetTargetNode(DGEdge<DDGNode, DDGEdge> *P) {
 350     return &P->getTargetNode();
 351   }
 352
 353   // Provide a mapped iterator so that the GraphTrait-based implementations can
 354   // find the target nodes without having to explicitly go through the edges.
 355   using ChildIteratorType =
 356       mapped_iterator<DDGNode::iterator, decltype(&DDGGetTargetNode)>;
 357   using ChildEdgeIteratorType = DDGNode::iterator;
 358
 359   static NodeRef getEntryNode(NodeRef N) { return N; }
 360   static ChildIteratorType child_begin(NodeRef N) {
 361     return ChildIteratorType(N->begin(), &DDGGetTargetNode);
 362   }
 363   static ChildIteratorType child_end(NodeRef N) {
 364     return ChildIteratorType(N->end(), &DDGGetTargetNode);
 365   }
 366
 367   static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
 368     return N->begin();
 369   }
 370   static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
 371 };
 372
 373 template <>
 374 struct GraphTraits<DataDependenceGraph *> : public GraphTraits<DDGNode *> {
 375   using nodes_iterator = DataDependenceGraph::iterator;
 376   static NodeRef getEntryNode(DataDependenceGraph *DG) {
 377     return &DG->getRoot();
 378   }
 379   static nodes_iterator nodes_begin(DataDependenceGraph *DG) {
 380     return DG->begin();
 381   }
 382   static nodes_iterator nodes_end(DataDependenceGraph *DG) { return DG->end(); }
 383 };
 384
 385 /// const versions of the grapth trait specializations for DDG
 386 template <> struct GraphTraits<const DDGNode *> {
 387   using NodeRef = const DDGNode *;
 388
 389   static const DDGNode *DDGGetTargetNode(const DGEdge<DDGNode, DDGEdge> *P) {
 390     return &P->getTargetNode();
 391   }
 392
 393   // Provide a mapped iterator so that the GraphTrait-based implementations can
 394   // find the target nodes without having to explicitly go through the edges.
 395   using ChildIteratorType =
 396       mapped_iterator<DDGNode::const_iterator, decltype(&DDGGetTargetNode)>;
 397   using ChildEdgeIteratorType = DDGNode::const_iterator;
 398
 399   static NodeRef getEntryNode(NodeRef N) { return N; }
 400   static ChildIteratorType child_begin(NodeRef N) {
 401     return ChildIteratorType(N->begin(), &DDGGetTargetNode);
 402   }
 403   static ChildIteratorType child_end(NodeRef N) {
 404     return ChildIteratorType(N->end(), &DDGGetTargetNode);
 405   }
 406
 407   static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
 408     return N->begin();
 409   }
 410   static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
 411 };
 412
 413 template <>
 414 struct GraphTraits<const DataDependenceGraph *>
 415     : public GraphTraits<const DDGNode *> {
 416   using nodes_iterator = DataDependenceGraph::const_iterator;
 417   static NodeRef getEntryNode(const DataDependenceGraph *DG) {
 418     return &DG->getRoot();
 419   }
 420   static nodes_iterator nodes_begin(const DataDependenceGraph *DG) {
 421     return DG->begin();
 422   }
 423   static nodes_iterator nodes_end(const DataDependenceGraph *DG) {
 424     return DG->end();
 425   }
 426 };
 427
 428 } // namespace llvm
 429
 430 #endif // LLVM_ANALYSIS_DDG_H