LLVM  14.0.0git
DDG.h
Go to the documentation of this file.
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"
21 #include "llvm/IR/Instructions.h"
22 
23 namespace llvm {
24 class DDGNode;
25 class 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. 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.
42 class DDGNode : public DDGNodeBase {
43 public:
45 
46  enum class NodeKind {
47  Unknown,
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 
62  Kind = N.Kind;
63  return *this;
64  }
65 
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 
81 protected:
82  /// Setter for the kind of this node.
83  void setKind(NodeKind K) { Kind = K; }
84 
85 private:
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.
91 class RootDDGNode : public DDGNode {
92 public:
94  RootDDGNode(const RootDDGNode &N) = delete;
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.
106 class SimpleDDGNode : public DDGNode {
107  friend class DDGBuilder;
108 
109 public:
110  SimpleDDGNode() = delete;
112  SimpleDDGNode(const SimpleDDGNode &N);
114  ~SimpleDDGNode();
115 
118  InstList = N.InstList;
119  return *this;
120  }
121 
124  InstList = std::move(N.InstList);
125  return *this;
126  }
127 
128  /// Get the list of instructions in this node.
130  assert(!InstList.empty() && "Instruction List is empty.");
131  return InstList;
132  }
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 
149 private:
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)
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}
172 class PiBlockDDGNode : public DDGNode {
173 public:
175 
176  PiBlockDDGNode() = delete;
177  PiBlockDDGNode(const PiNodeList &List);
180  ~PiBlockDDGNode();
181 
184  NodeList = N.NodeList;
185  return *this;
186  }
187 
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  }
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 
209 private:
210  /// List of nodes in this pi-block.
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.
219 class DDGEdge : public DDGEdgeBase {
220 public:
221  /// The kind of edge in the DDG
222  enum class EdgeKind {
223  Unknown,
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) {}
236  Kind = E.Kind;
237  return *this;
238  }
239 
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 
259 private:
260  EdgeKind Kind;
261 };
262 
263 /// Encapsulate some common data and functionality needed for different
264 /// variations of data dependence graphs.
265 template <typename NodeType> class DependenceGraphInfo {
266 public:
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) {}
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 
299 protected:
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.
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 
314 
315 /// Data Dependency Graph
316 class DataDependenceGraph : public DDGBase, public DDGInfo {
318  friend class DDGBuilder;
319 
320 public:
321  using NodeType = DDGNode;
322  using EdgeType = DDGEdge;
323 
324  DataDependenceGraph() = delete;
325  DataDependenceGraph(const DataDependenceGraph &G) = delete;
327  : DDGBase(std::move(G)), DDGInfo(std::move(G)) {}
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 
336 protected:
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 
342 private:
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.
356 class DDGBuilder : public AbstractDependenceGraphBuilder<DataDependenceGraph> {
357 public:
359  const BasicBlockListType &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  }
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 {
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 
414 raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N);
415 raw_ostream &operator<<(raw_ostream &OS, const DDGNode::NodeKind K);
416 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge &E);
417 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K);
419 
420 //===--------------------------------------------------------------------===//
421 // DDG Analysis Passes
422 //===--------------------------------------------------------------------===//
423 
424 /// Analysis pass that builds the DDG for a loop.
426 public:
427  using Result = std::unique_ptr<DataDependenceGraph>;
429 
430 private:
432  static AnalysisKey Key;
433 };
434 
435 /// Textual printer pass for the DDG of a loop.
436 class DDGAnalysisPrinterPass : public PassInfoMixin<DDGAnalysisPrinterPass> {
437 public:
438  explicit DDGAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
441 
442 private:
443  raw_ostream &OS;
444 };
445 
446 //===--------------------------------------------------------------------===//
447 // DependenceGraphInfo Implementation
448 //===--------------------------------------------------------------------===//
449 
450 template <typename NodeType>
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 
472 template <typename NodeType>
473 std::string
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
497 template <> struct GraphTraits<DDGNode *> {
498  using NodeRef = DDGNode *;
499 
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)>;
509 
510  static NodeRef getEntryNode(NodeRef N) { return N; }
512  return ChildIteratorType(N->begin(), &DDGGetTargetNode);
513  }
515  return ChildIteratorType(N->end(), &DDGGetTargetNode);
516  }
517 
519  return N->begin();
520  }
521  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
522 };
523 
524 template <>
528  return &DG->getRoot();
529  }
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
537 template <> struct GraphTraits<const DDGNode *> {
538  using NodeRef = const DDGNode *;
539 
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)>;
549 
550  static NodeRef getEntryNode(NodeRef N) { return N; }
552  return ChildIteratorType(N->begin(), &DDGGetTargetNode);
553  }
555  return ChildIteratorType(N->end(), &DDGGetTargetNode);
556  }
557 
559  return N->begin();
560  }
561  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
562 };
563 
564 template <>
569  return &DG->getRoot();
570  }
572  return DG->begin();
573  }
575  return DG->end();
576  }
577 };
578 
579 } // namespace llvm
580 
581 #endif // LLVM_ANALYSIS_DDG_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::DDGBuilder::DDGBuilder
DDGBuilder(DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs)
Definition: DDG.h:358
llvm::DependenceGraphInfo
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Definition: DDG.h:265
llvm::RootDDGNode
Subclass of DDGNode representing the root node of the graph.
Definition: DDG.h:91
llvm::DDGNode::getKind
NodeKind getKind() const
Getter for the kind of this node.
Definition: DDG.h:73
llvm::SimpleDDGNode::classof
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:143
llvm::DDGEdge::operator=
DDGEdge & operator=(DDGEdge &&E)
Definition: DDG.h:240
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::GraphTraits< DataDependenceGraph * >::nodes_begin
static nodes_iterator nodes_begin(DataDependenceGraph *DG)
Definition: DDG.h:530
llvm::GraphTraits< const DataDependenceGraph * >::nodes_iterator
DataDependenceGraph::const_iterator nodes_iterator
Definition: DDG.h:567
llvm::DDGEdge::EdgeKind::Rooted
@ Rooted
llvm::DDGBuilder::createPiBlock
DDGNode & createPiBlock(const NodeListType &L) final override
Create a pi-block node in the graph representing a group of nodes in an SCC of the graph.
Definition: DDG.h:373
llvm::DirectedGraph::connect
bool connect(NodeType &Src, NodeType &Dst, EdgeType &E)
Assuming nodes Src and Dst are already in the graph, connect node Src to node Dst using the provided ...
Definition: DirectedGraph.h:264
llvm::DDGNode::~DDGNode
virtual ~DDGNode()=0
Definition: DDG.cpp:37
llvm::DDGEdge::DDGEdge
DDGEdge(DDGNode &N, EdgeKind K)
Definition: DDG.h:231
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:374
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::DependenceGraphInfo::Name
std::string Name
Definition: DDG.h:301
llvm::DDGBuilder::shouldCreatePiBlocks
bool shouldCreatePiBlocks() const final override
Definition: DDG.cpp:302
llvm::SimpleDDGNode::~SimpleDDGNode
~SimpleDDGNode()
Definition: DDG.cpp:128
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:625
llvm::SmallVector< DDGNode *, 4 >
llvm::DDGBuilder::createRootNode
DDGNode & createRootNode() final override
Create the root node of the graph.
Definition: DDG.h:361
llvm::DDGNode::operator=
DDGNode & operator=(DDGNode &&N)
Definition: DDG.h:66
llvm::DDGEdge::getKind
EdgeKind getKind() const
Get the edge kind.
Definition: DDG.h:247
llvm::DGNode
Represent a node in the directed graph.
Definition: DirectedGraph.h:72
llvm::GraphTraits< const DDGNode * >::ChildEdgeIteratorType
DDGNode::const_iterator ChildEdgeIteratorType
Definition: DDG.h:548
llvm::GraphTraits< const DDGNode * >::DDGGetTargetNode
static const DDGNode * DDGGetTargetNode(const DGEdge< DDGNode, DDGEdge > *P)
Definition: DDG.h:540
llvm::GraphTraits< DDGNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: DDG.h:510
llvm::SimpleDDGNode::SimpleDDGNode
SimpleDDGNode()=delete
llvm::DirectedGraph::begin
const_iterator begin() const
Definition: DirectedGraph.h:194
llvm::interleaveComma
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
Definition: STLExtras.h:1832
llvm::PiBlockDDGNode::~PiBlockDDGNode
~PiBlockDDGNode()
Definition: DDG.cpp:151
llvm::DDGNode::DDGNode
DDGNode(const NodeKind K)
Definition: DDG.h:55
DenseMap.h
llvm::GraphTraits< const DataDependenceGraph * >::nodes_end
static nodes_iterator nodes_end(const DataDependenceGraph *DG)
Definition: DDG.h:574
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::DependenceGraphInfo::getDependencies
bool getDependencies(const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const
Collect all the data dependency infos coming from any pair of memory accesses from Src to Dst,...
Definition: DDG.h:451
llvm::mapped_iterator
Definition: STLExtras.h:277
llvm::PiBlockDDGNode::operator=
PiBlockDDGNode & operator=(const PiBlockDDGNode &N)
Definition: DDG.h:182
llvm::GraphTraits< DataDependenceGraph * >::getEntryNode
static NodeRef getEntryNode(DataDependenceGraph *DG)
Definition: DDG.h:527
llvm::PiBlockDDGNode::PiNodeList
SmallVector< DDGNode *, 4 > PiNodeList
Definition: DDG.h:174
llvm::DependenceGraphInfo::getDependenceString
std::string getDependenceString(const NodeType &Src, const NodeType &Dst) const
Return a string representing the type of dependence that the dependence analysis identified between t...
Definition: DDG.h:474
llvm::SimpleDDGNode::operator=
SimpleDDGNode & operator=(const SimpleDDGNode &N)
Definition: DDG.h:116
llvm::DataDependenceGraph::~DataDependenceGraph
~DataDependenceGraph()
Definition: DDG.cpp:213
llvm::DDGEdge::DDGEdge
DDGEdge(DDGNode &N)=delete
llvm::GraphTraits< const DDGNode * >::child_edge_end
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: DDG.h:561
llvm::DDGEdge::isMemoryDependence
bool isMemoryDependence() const
Return true if this is a memory dependence edge, and false otherwise.
Definition: DDG.h:253
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::DataDependenceGraph::DataDependenceGraph
DataDependenceGraph(DataDependenceGraph &&G)
Definition: DDG.h:326
llvm::GraphTraits< const DDGNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: DDG.h:550
LoopAnalysisManager.h
llvm::DDGBuilder::createRootedEdge
DDGEdge & createRootedEdge(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.h:391
llvm::DependenceGraphInfo::DependenceGraphInfo
DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
Definition: DDG.h:271
DependenceGraphBuilder.h
llvm::DDGEdge::operator=
DDGEdge & operator=(const DDGEdge &E)
Definition: DDG.h:234
DirectedGraph.h
llvm::DirectedGraph::const_iterator
typename NodeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:178
llvm::DDGNode::DDGNode
DDGNode(DDGNode &&N)
Definition: DDG.h:57
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::RootDDGNode::~RootDDGNode
~RootDDGNode()
Definition: DDG.h:96
llvm::PiBlockDDGNode::getNodes
const PiNodeList & getNodes() const
Get the list of nodes in this pi-block.
Definition: DDG.h:195
llvm::DDGEdge
Data Dependency Graph Edge.
Definition: DDG.h:219
llvm::SimpleDDGNode::operator=
SimpleDDGNode & operator=(SimpleDDGNode &&N)
Definition: DDG.h:122
llvm::GraphTraits< const DataDependenceGraph * >::nodes_begin
static nodes_iterator nodes_begin(const DataDependenceGraph *DG)
Definition: DDG.h:571
llvm::DependenceGraphInfo::getRoot
NodeType & getRoot() const
Return the root node of the graph.
Definition: DDG.h:281
llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::DI
DependenceInfo & DI
Dependence information used to create memory dependence edges in the graph.
Definition: DependenceGraphBuilder.h:184
llvm::DDGEdge::EdgeKind::RegisterDefUse
@ RegisterDefUse
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:481
llvm::DDGBuilder::createMemoryEdge
DDGEdge & createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.h:385
llvm::SimpleDDGNode::classof
static bool classof(const SimpleDDGNode *N)
Definition: DDG.h:147
NodeList
Definition: MicrosoftDemangle.cpp:37
llvm::ISD::NodeType
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
Definition: ISDOpcodes.h:40
llvm::Instruction
Definition: Instruction.h:45
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::PiBlockDDGNode::classof
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:205
llvm::DirectedGraph::iterator
typename NodeListTy::iterator iterator
Definition: DirectedGraph.h:177
llvm::GraphTraits< DDGNode * >::child_edge_end
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: DDG.h:521
llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
llvm::DependenceGraphInfo::~DependenceGraphInfo
virtual ~DependenceGraphInfo()
Definition: DDG.h:275
llvm::DirectedGraph::end
const_iterator end() const
Definition: DirectedGraph.h:195
llvm::PiBlockDDGNode::PiBlockDDGNode
PiBlockDDGNode()=delete
llvm::DDGAnalysisPrinterPass::DDGAnalysisPrinterPass
DDGAnalysisPrinterPass(raw_ostream &OS)
Definition: DDG.h:438
llvm::DataDependenceGraph::DataDependenceGraph
DataDependenceGraph()=delete
llvm::GraphTraits< const DDGNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: DDG.h:551
llvm::GraphTraits< DDGNode * >::DDGGetTargetNode
static DDGNode * DDGGetTargetNode(DGEdge< DDGNode, DDGEdge > *P)
Definition: DDG.h:500
llvm::GraphTraits< const DataDependenceGraph * >::getEntryNode
static NodeRef getEntryNode(const DataDependenceGraph *DG)
Definition: DDG.h:568
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::DirectedGraph
Directed graph.
Definition: DirectedGraph.h:172
llvm::PiBlockDDGNode
Subclass of DDGNode representing a pi-block.
Definition: DDG.h:172
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::DependenceInfo
DependenceInfo - This class is the main dependence-analysis driver.
Definition: DependenceAnalysis.h:272
llvm::DDGNode::NodeKind::PiBlock
@ PiBlock
llvm::DataDependenceGraph::addNode
bool addNode(NodeType &N)
Add node N to the graph, if it's not added yet, and keep track of the root node as well as pi-blocks ...
Definition: DDG.cpp:221
llvm::GraphTraits< const DDGNode * >
const versions of the grapth trait specializations for DDG
Definition: DDG.h:537
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:249
llvm::SimpleDDGNode
Subclass of DDGNode representing single or multi-instruction nodes.
Definition: DDG.h:106
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::GraphTraits< DDGNode * >::child_edge_begin
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: DDG.h:518
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::DependenceGraphInfo::DependenceList
SmallVector< std::unique_ptr< Dependence >, 1 > DependenceList
Definition: DDG.h:267
llvm::RootDDGNode::RootDDGNode
RootDDGNode()
Definition: DDG.h:93
llvm::DenseMap< const NodeType *, const PiBlockDDGNode * >
llvm::DDGEdge::DDGEdge
DDGEdge(DDGEdge &&E)
Definition: DDG.h:233
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::GraphTraits< DDGNode * >::ChildEdgeIteratorType
DDGNode::iterator ChildEdgeIteratorType
Definition: DDG.h:508
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DGNode::operator=
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &N)
Definition: DirectedGraph.h:85
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1609
llvm::DDGBuilder::createDefUseEdge
DDGEdge & createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.h:379
llvm::DataDependenceGraph::NodeType
DDGNode NodeType
Definition: DDG.h:321
llvm::DDGEdge::EdgeKind::Last
@ Last
llvm::DDGNode::NodeKind::SingleInstruction
@ SingleInstruction
llvm::DependenceGraphInfo::getName
StringRef getName() const
Return the label that is used to name this graph.
Definition: DDG.h:278
llvm::GraphTraits< DataDependenceGraph * >::nodes_iterator
DataDependenceGraph::iterator nodes_iterator
Definition: DDG.h:526
llvm::DDGAnalysisPrinterPass
Textual printer pass for the DDG of a loop.
Definition: DDG.h:436
llvm::DDGEdge::isDefUse
bool isDefUse() const
Return true if this is a def-use edge, and false otherwise.
Definition: DDG.h:250
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:397
llvm::DDGNode::NodeKind::Root
@ Root
llvm::DDGNode::DDGNode
DDGNode(const DDGNode &N)
Definition: DDG.h:56
llvm::DDGNode::DDGNode
DDGNode()=delete
llvm::DDGEdge::isRooted
bool isRooted() const
Return true if this is an edge stemming from the root node, and false otherwise.
Definition: DDG.h:257
llvm::LoopInfo
Definition: LoopInfo.h:1083
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1748
llvm::DDGNode::collectInstructions
bool collectInstructions(llvm::function_ref< bool(Instruction *)> const &Pred, InstructionListType &IList) const
Collect a list of instructions, in IList, for which predicate Pred evaluates to true when iterating o...
Definition: DDG.cpp:39
llvm::GraphTraits< DataDependenceGraph * >::nodes_end
static nodes_iterator nodes_end(DataDependenceGraph *DG)
Definition: DDG.h:533
llvm::DGNode::const_iterator
typename EdgeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:76
llvm::RootDDGNode::RootDDGNode
RootDDGNode(RootDDGNode &&N)
Definition: DDG.h:95
llvm::SimpleDDGNode::getInstructions
InstructionListType & getInstructions()
Definition: DDG.h:133
llvm::DDGBuilder::areNodesMergeable
bool areNodesMergeable(const DDGNode &Src, const DDGNode &Tgt) const final override
Return true if the two nodes \pSrc and \pTgt are both simple nodes and the consecutive instructions a...
Definition: DDG.cpp:267
llvm::DependenceGraphInfo::Root
NodeType * Root
Definition: DDG.h:310
NodeKind
Determine the kind of a node from its type.
Definition: ItaniumDemangle.h:2364
llvm::DDGBuilder::createFineGrainedNode
DDGNode & createFineGrainedNode(Instruction &I) final override
Create an atomic node in the graph given a single instruction.
Definition: DDG.h:367
std
Definition: BitVector.h:838
llvm::RootDDGNode::classof
static bool classof(const RootDDGNode *N)
Definition: DDG.h:102
llvm::SimpleDDGNode::getLastInstruction
Instruction * getLastInstruction() const
Definition: DDG.h:140
llvm::DDGEdge::DDGEdge
DDGEdge(const DDGEdge &E)
Definition: DDG.h:232
llvm::DDGNode::NodeKind::MultiInstruction
@ MultiInstruction
llvm::GraphTraits< const DDGNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: DDG.h:554
llvm::DependenceGraphInfo::DependenceGraphInfo
DependenceGraphInfo(DependenceGraphInfo &&G)
Definition: DDG.h:273
llvm::DDGEdge::EdgeKind::Unknown
@ Unknown
llvm::PiBlockDDGNode::operator=
PiBlockDDGNode & operator=(PiBlockDDGNode &&N)
Definition: DDG.h:188
llvm::GraphTraits< DDGNode * >
non-const versions of the grapth trait specializations for DDG
Definition: DDG.h:497
llvm::DependenceGraphInfo::DI
const DependenceInfo DI
Definition: DDG.h:306
llvm::PiBlockDDGNode::getNodes
PiNodeList & getNodes()
Definition: DDG.h:199
llvm::DependenceInfo::depends
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
Definition: DependenceAnalysis.cpp:3525
llvm::GraphTraits< DDGNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: DDG.h:511
Instructions.h
llvm::DDGNode
Data Dependence Graph Node The graph can represent the following types of nodes:
Definition: DDG.h:42
llvm::DGEdge::operator=
DGEdge< NodeType, EdgeType > & operator=(const DGEdge< NodeType, EdgeType > &E)
Definition: DirectedGraph.h:34
N
#define N
llvm::DGNode::iterator
typename EdgeListTy::iterator iterator
Definition: DirectedGraph.h:75
llvm::DataDependenceGraph
Data Dependency Graph.
Definition: DDG.h:316
llvm::DDGBuilder::getNodesInPiBlock
const NodeListType & getNodesInPiBlock(const DDGNode &N) final override
Definition: DDG.h:399
llvm::SmallVectorImpl< Instruction * >
llvm::SimpleDDGNode::getFirstInstruction
Instruction * getFirstInstruction() const
Get the first/last instruction in the node.
Definition: DDG.h:139
llvm::DDGEdge::EdgeKind::MemoryDependence
@ MemoryDependence
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::DDGBuilder::shouldSimplify
bool shouldSimplify() const final override
Definition: DDG.cpp:300
InstructionListType
SmallVector< Instruction *, 2 > InstructionListType
Definition: DependenceGraphBuilder.cpp:34
llvm::DDGNode::setKind
void setKind(NodeKind K)
Setter for the kind of this node.
Definition: DDG.h:83
llvm::DGEdge
Represent an edge in the directed graph.
Definition: DirectedGraph.h:27
RN
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
Definition: README_P9.txt:262
llvm::GraphTraits
Definition: GraphTraits.h:35
DependenceAnalysis.h
llvm::DDGAnalysis
Analysis pass that builds the DDG for a loop.
Definition: DDG.h:425
llvm::DDGAnalysis::Result
std::unique_ptr< DataDependenceGraph > Result
Definition: DDG.h:427
llvm::DDGBuilder
Concrete implementation of a pure data dependence graph builder.
Definition: DDG.h:356
llvm::GraphTraits< DDGNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: DDG.h:514
llvm::raw_string_ostream::str
std::string & str()
Flushes the stream contents to the target string and returns the string's reference.
Definition: raw_ostream.h:643
llvm::DDGNode::NodeKind::Unknown
@ Unknown
llvm::DDGNode::operator=
DDGNode & operator=(const DDGNode &N)
Definition: DDG.h:60
llvm::DDGBuilder::mergeNodes
void mergeNodes(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.cpp:280
llvm::GraphTraits< const DDGNode * >::child_edge_begin
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: DDG.h:558
llvm::DataDependenceGraph::getPiBlock
const PiBlockDDGNode * getPiBlock(const NodeType &N) const
If node N belongs to a pi-block return a pointer to the pi-block, otherwise return null.
Definition: DDG.cpp:244
llvm::DependenceGraphInfo::DependenceGraphInfo
DependenceGraphInfo()=delete
llvm::DDGEdge::EdgeKind
EdgeKind
The kind of edge in the DDG.
Definition: DDG.h:222
llvm::SimpleDDGNode::getInstructions
const InstructionListType & getInstructions() const
Get the list of instructions in this node.
Definition: DDG.h:129
llvm::RootDDGNode::classof
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:99
llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph
DataDependenceGraph & Graph
Reference to the graph that gets built by a concrete implementation of this builder.
Definition: DependenceGraphBuilder.h:180