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