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