LLVM  15.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 
22 namespace llvm {
23 class Function;
24 class Loop;
25 class LoopInfo;
26 class DDGNode;
27 class DDGEdge;
31 class LPMUpdater;
32 
33 /// Data Dependence Graph Node
34 /// The graph can represent the following types of nodes:
35 /// 1. Single instruction node containing just one instruction.
36 /// 2. Multiple instruction node where two or more instructions from
37 /// the same basic block are merged into one node.
38 /// 3. Pi-block node which is a group of other DDG nodes that are part of a
39 /// strongly-connected component of the graph.
40 /// A pi-block node contains more than one single or multiple instruction
41 /// nodes. The root node cannot be part of a pi-block.
42 /// 4. Root node is a special node that connects to all components such that
43 /// there is always a path from it to any node in the graph.
44 class DDGNode : public DDGNodeBase {
45 public:
47 
48  enum class NodeKind {
49  Unknown,
52  PiBlock,
53  Root,
54  };
55 
56  DDGNode() = delete;
57  DDGNode(const NodeKind K) : Kind(K) {}
58  DDGNode(const DDGNode &N) = default;
59  DDGNode(DDGNode &&N) : DDGNodeBase(std::move(N)), Kind(N.Kind) {}
60  virtual ~DDGNode() = 0;
61 
64  Kind = N.Kind;
65  return *this;
66  }
67 
70  Kind = N.Kind;
71  return *this;
72  }
73 
74  /// Getter for the kind of this node.
75  NodeKind getKind() const { return Kind; }
76 
77  /// Collect a list of instructions, in \p IList, for which predicate \p Pred
78  /// evaluates to true when iterating over instructions of this node. Return
79  /// true if at least one instruction was collected, and false otherwise.
80  bool collectInstructions(llvm::function_ref<bool(Instruction *)> const &Pred,
81  InstructionListType &IList) const;
82 
83 protected:
84  /// Setter for the kind of this node.
85  void setKind(NodeKind K) { Kind = K; }
86 
87 private:
88  NodeKind Kind;
89 };
90 
91 /// Subclass of DDGNode representing the root node of the graph.
92 /// There should only be one such node in a given graph.
93 class RootDDGNode : public DDGNode {
94 public:
96  RootDDGNode(const RootDDGNode &N) = delete;
98  ~RootDDGNode() = default;
99 
100  /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
101  static bool classof(const DDGNode *N) {
102  return N->getKind() == NodeKind::Root;
103  }
104  static bool classof(const RootDDGNode *N) { return true; }
105 };
106 
107 /// Subclass of DDGNode representing single or multi-instruction nodes.
108 class SimpleDDGNode : public DDGNode {
109  friend class DDGBuilder;
110 
111 public:
112  SimpleDDGNode() = delete;
114  SimpleDDGNode(const SimpleDDGNode &N);
116  ~SimpleDDGNode();
117 
118  SimpleDDGNode &operator=(const SimpleDDGNode &N) = default;
119 
122  InstList = std::move(N.InstList);
123  return *this;
124  }
125 
126  /// Get the list of instructions in this node.
128  assert(!InstList.empty() && "Instruction List is empty.");
129  return InstList;
130  }
132  return const_cast<InstructionListType &>(
133  static_cast<const SimpleDDGNode *>(this)->getInstructions());
134  }
135 
136  /// Get the first/last instruction in the node.
137  Instruction *getFirstInstruction() const { return getInstructions().front(); }
138  Instruction *getLastInstruction() const { return getInstructions().back(); }
139 
140  /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
141  static bool classof(const DDGNode *N) {
142  return N->getKind() == NodeKind::SingleInstruction ||
143  N->getKind() == NodeKind::MultiInstruction;
144  }
145  static bool classof(const SimpleDDGNode *N) { return true; }
146 
147 private:
148  /// Append the list of instructions in \p Input to this node.
149  void appendInstructions(const InstructionListType &Input) {
150  setKind((InstList.size() == 0 && Input.size() == 1)
153  llvm::append_range(InstList, Input);
154  }
155  void appendInstructions(const SimpleDDGNode &Input) {
156  appendInstructions(Input.getInstructions());
157  }
158 
159  /// List of instructions associated with a single or multi-instruction node.
160  SmallVector<Instruction *, 2> InstList;
161 };
162 
163 /// Subclass of DDGNode representing a pi-block. A pi-block represents a group
164 /// of DDG nodes that are part of a strongly-connected component of the graph.
165 /// Replacing all the SCCs with pi-blocks results in an acyclic representation
166 /// of the DDG. For example if we have:
167 /// {a -> b}, {b -> c, d}, {c -> a}
168 /// the cycle a -> b -> c -> a is abstracted into a pi-block "p" as follows:
169 /// {p -> d} with "p" containing: {a -> b}, {b -> c}, {c -> a}
170 class PiBlockDDGNode : public DDGNode {
171 public:
173 
174  PiBlockDDGNode() = delete;
175  PiBlockDDGNode(const PiNodeList &List);
178  ~PiBlockDDGNode();
179 
180  PiBlockDDGNode &operator=(const PiBlockDDGNode &N) = default;
181 
184  NodeList = std::move(N.NodeList);
185  return *this;
186  }
187 
188  /// Get the list of nodes in this pi-block.
189  const PiNodeList &getNodes() const {
190  assert(!NodeList.empty() && "Node list is empty.");
191  return NodeList;
192  }
194  return const_cast<PiNodeList &>(
195  static_cast<const PiBlockDDGNode *>(this)->getNodes());
196  }
197 
198  /// Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
199  static bool classof(const DDGNode *N) {
200  return N->getKind() == NodeKind::PiBlock;
201  }
202 
203 private:
204  /// List of nodes in this pi-block.
206 };
207 
208 /// Data Dependency Graph Edge.
209 /// An edge in the DDG can represent a def-use relationship or
210 /// a memory dependence based on the result of DependenceAnalysis.
211 /// A rooted edge connects the root node to one of the components
212 /// of the graph.
213 class DDGEdge : public DDGEdgeBase {
214 public:
215  /// The kind of edge in the DDG
216  enum class EdgeKind {
217  Unknown,
220  Rooted,
221  Last = Rooted // Must be equal to the largest enum value.
222  };
223 
224  explicit DDGEdge(DDGNode &N) = delete;
225  DDGEdge(DDGNode &N, EdgeKind K) : DDGEdgeBase(N), Kind(K) {}
226  DDGEdge(const DDGEdge &E) : DDGEdgeBase(E), Kind(E.getKind()) {}
227  DDGEdge(DDGEdge &&E) : DDGEdgeBase(std::move(E)), Kind(E.Kind) {}
228  DDGEdge &operator=(const DDGEdge &E) = default;
229 
232  Kind = E.Kind;
233  return *this;
234  }
235 
236  /// Get the edge kind
237  EdgeKind getKind() const { return Kind; };
238 
239  /// Return true if this is a def-use edge, and false otherwise.
240  bool isDefUse() const { return Kind == EdgeKind::RegisterDefUse; }
241 
242  /// Return true if this is a memory dependence edge, and false otherwise.
243  bool isMemoryDependence() const { return Kind == EdgeKind::MemoryDependence; }
244 
245  /// Return true if this is an edge stemming from the root node, and false
246  /// otherwise.
247  bool isRooted() const { return Kind == EdgeKind::Rooted; }
248 
249 private:
250  EdgeKind Kind;
251 };
252 
253 /// Encapsulate some common data and functionality needed for different
254 /// variations of data dependence graphs.
255 template <typename NodeType> class DependenceGraphInfo {
256 public:
258 
259  DependenceGraphInfo() = delete;
260  DependenceGraphInfo(const DependenceGraphInfo &G) = delete;
261  DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
262  : Name(N), DI(DepInfo), Root(nullptr) {}
264  : Name(std::move(G.Name)), DI(std::move(G.DI)), Root(G.Root) {}
265  virtual ~DependenceGraphInfo() = default;
266 
267  /// Return the label that is used to name this graph.
268  StringRef getName() const { return Name; }
269 
270  /// Return the root node of the graph.
271  NodeType &getRoot() const {
272  assert(Root && "Root node is not available yet. Graph construction may "
273  "still be in progress\n");
274  return *Root;
275  }
276 
277  /// Collect all the data dependency infos coming from any pair of memory
278  /// accesses from \p Src to \p Dst, and store them into \p Deps. Return true
279  /// if a dependence exists, and false otherwise.
280  bool getDependencies(const NodeType &Src, const NodeType &Dst,
281  DependenceList &Deps) const;
282 
283  /// Return a string representing the type of dependence that the dependence
284  /// analysis identified between the two given nodes. This function assumes
285  /// that there is a memory dependence between the given two nodes.
286  std::string getDependenceString(const NodeType &Src,
287  const NodeType &Dst) const;
288 
289 protected:
290  // Name of the graph.
291  std::string Name;
292 
293  // Store a copy of DependenceInfo in the graph, so that individual memory
294  // dependencies don't need to be stored. Instead when the dependence is
295  // queried it is recomputed using @DI.
297 
298  // A special node in the graph that has an edge to every connected component of
299  // the graph, to ensure all nodes are reachable in a graph walk.
300  NodeType *Root = nullptr;
301 };
302 
304 
305 /// Data Dependency Graph
306 class DataDependenceGraph : public DDGBase, public DDGInfo {
308  friend class DDGBuilder;
309 
310 public:
311  using NodeType = DDGNode;
312  using EdgeType = DDGEdge;
313 
314  DataDependenceGraph() = delete;
315  DataDependenceGraph(const DataDependenceGraph &G) = delete;
317  : DDGBase(std::move(G)), DDGInfo(std::move(G)) {}
321 
322  /// If node \p N belongs to a pi-block return a pointer to the pi-block,
323  /// otherwise return null.
324  const PiBlockDDGNode *getPiBlock(const NodeType &N) const;
325 
326 protected:
327  /// Add node \p N to the graph, if it's not added yet, and keep track of the
328  /// root node as well as pi-blocks and their members. Return true if node is
329  /// successfully added.
330  bool addNode(NodeType &N);
331 
332 private:
334 
335  /// Mapping from graph nodes to their containing pi-blocks. If a node is not
336  /// part of a pi-block, it will not appear in this map.
337  PiBlockMapType PiBlockMap;
338 };
339 
340 /// Concrete implementation of a pure data dependence graph builder. This class
341 /// provides custom implementation for the pure-virtual functions used in the
342 /// generic dependence graph build algorithm.
343 ///
344 /// For information about time complexity of the build algorithm see the
345 /// comments near the declaration of AbstractDependenceGraphBuilder.
346 class DDGBuilder : public AbstractDependenceGraphBuilder<DataDependenceGraph> {
347 public:
349  const BasicBlockListType &BBs)
351  DDGNode &createRootNode() final override {
352  auto *RN = new RootDDGNode();
353  assert(RN && "Failed to allocate memory for DDG root node.");
354  Graph.addNode(*RN);
355  return *RN;
356  }
358  auto *SN = new SimpleDDGNode(I);
359  assert(SN && "Failed to allocate memory for simple DDG node.");
360  Graph.addNode(*SN);
361  return *SN;
362  }
363  DDGNode &createPiBlock(const NodeListType &L) final override {
364  auto *Pi = new PiBlockDDGNode(L);
365  assert(Pi && "Failed to allocate memory for pi-block node.");
366  Graph.addNode(*Pi);
367  return *Pi;
368  }
369  DDGEdge &createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final override {
370  auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::RegisterDefUse);
371  assert(E && "Failed to allocate memory for edge");
372  Graph.connect(Src, Tgt, *E);
373  return *E;
374  }
375  DDGEdge &createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final override {
377  assert(E && "Failed to allocate memory for edge");
378  Graph.connect(Src, Tgt, *E);
379  return *E;
380  }
381  DDGEdge &createRootedEdge(DDGNode &Src, DDGNode &Tgt) final override {
382  auto *E = new DDGEdge(Tgt, DDGEdge::EdgeKind::Rooted);
383  assert(E && "Failed to allocate memory for edge");
384  assert(isa<RootDDGNode>(Src) && "Expected root node");
385  Graph.connect(Src, Tgt, *E);
386  return *E;
387  }
388 
389  const NodeListType &getNodesInPiBlock(const DDGNode &N) final override {
390  auto *PiNode = dyn_cast<const PiBlockDDGNode>(&N);
391  assert(PiNode && "Expected a pi-block node.");
392  return PiNode->getNodes();
393  }
394 
395  /// Return true if the two nodes \pSrc and \pTgt are both simple nodes and
396  /// the consecutive instructions after merging belong to the same basic block.
397  bool areNodesMergeable(const DDGNode &Src,
398  const DDGNode &Tgt) const final override;
399  void mergeNodes(DDGNode &Src, DDGNode &Tgt) final override;
400  bool shouldSimplify() const final override;
401  bool shouldCreatePiBlocks() const final override;
402 };
403 
404 raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N);
405 raw_ostream &operator<<(raw_ostream &OS, const DDGNode::NodeKind K);
406 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge &E);
407 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K);
409 
410 //===--------------------------------------------------------------------===//
411 // DDG Analysis Passes
412 //===--------------------------------------------------------------------===//
413 
414 /// Analysis pass that builds the DDG for a loop.
416 public:
417  using Result = std::unique_ptr<DataDependenceGraph>;
419 
420 private:
422  static AnalysisKey Key;
423 };
424 
425 /// Textual printer pass for the DDG of a loop.
426 class DDGAnalysisPrinterPass : public PassInfoMixin<DDGAnalysisPrinterPass> {
427 public:
428  explicit DDGAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
431 
432 private:
433  raw_ostream &OS;
434 };
435 
436 //===--------------------------------------------------------------------===//
437 // DependenceGraphInfo Implementation
438 //===--------------------------------------------------------------------===//
439 
440 template <typename NodeType>
442  const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const {
443  assert(Deps.empty() && "Expected empty output list at the start.");
444 
445  // List of memory access instructions from src and dst nodes.
446  SmallVector<Instruction *, 8> SrcIList, DstIList;
447  auto isMemoryAccess = [](const Instruction *I) {
448  return I->mayReadOrWriteMemory();
449  };
450  Src.collectInstructions(isMemoryAccess, SrcIList);
451  Dst.collectInstructions(isMemoryAccess, DstIList);
452 
453  for (auto *SrcI : SrcIList)
454  for (auto *DstI : DstIList)
455  if (auto Dep =
456  const_cast<DependenceInfo *>(&DI)->depends(SrcI, DstI, true))
457  Deps.push_back(std::move(Dep));
458 
459  return !Deps.empty();
460 }
461 
462 template <typename NodeType>
463 std::string
465  const NodeType &Dst) const {
466  std::string Str;
467  raw_string_ostream OS(Str);
468  DependenceList Deps;
469  if (!getDependencies(Src, Dst, Deps))
470  return OS.str();
471  interleaveComma(Deps, OS, [&](const std::unique_ptr<Dependence> &D) {
472  D->dump(OS);
473  // Remove the extra new-line character printed by the dump
474  // method
475  if (OS.str().back() == '\n')
476  OS.str().pop_back();
477  });
478 
479  return OS.str();
480 }
481 
482 //===--------------------------------------------------------------------===//
483 // GraphTraits specializations for the DDG
484 //===--------------------------------------------------------------------===//
485 
486 /// non-const versions of the grapth trait specializations for DDG
487 template <> struct GraphTraits<DDGNode *> {
488  using NodeRef = DDGNode *;
489 
491  return &P->getTargetNode();
492  }
493 
494  // Provide a mapped iterator so that the GraphTrait-based implementations can
495  // find the target nodes without having to explicitly go through the edges.
496  using ChildIteratorType =
497  mapped_iterator<DDGNode::iterator, decltype(&DDGGetTargetNode)>;
499 
500  static NodeRef getEntryNode(NodeRef N) { return N; }
502  return ChildIteratorType(N->begin(), &DDGGetTargetNode);
503  }
505  return ChildIteratorType(N->end(), &DDGGetTargetNode);
506  }
507 
509  return N->begin();
510  }
511  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
512 };
513 
514 template <>
518  return &DG->getRoot();
519  }
521  return DG->begin();
522  }
523  static nodes_iterator nodes_end(DataDependenceGraph *DG) { return DG->end(); }
524 };
525 
526 /// const versions of the grapth trait specializations for DDG
527 template <> struct GraphTraits<const DDGNode *> {
528  using NodeRef = const DDGNode *;
529 
531  return &P->getTargetNode();
532  }
533 
534  // Provide a mapped iterator so that the GraphTrait-based implementations can
535  // find the target nodes without having to explicitly go through the edges.
536  using ChildIteratorType =
537  mapped_iterator<DDGNode::const_iterator, decltype(&DDGGetTargetNode)>;
539 
540  static NodeRef getEntryNode(NodeRef N) { return N; }
542  return ChildIteratorType(N->begin(), &DDGGetTargetNode);
543  }
545  return ChildIteratorType(N->end(), &DDGGetTargetNode);
546  }
547 
549  return N->begin();
550  }
551  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
552 };
553 
554 template <>
559  return &DG->getRoot();
560  }
562  return DG->begin();
563  }
565  return DG->end();
566  }
567 };
568 
569 } // namespace llvm
570 
571 #endif // LLVM_ANALYSIS_DDG_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::DDGBuilder::DDGBuilder
DDGBuilder(DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs)
Definition: DDG.h:348
llvm::DependenceGraphInfo
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Definition: DDG.h:255
llvm::RootDDGNode
Subclass of DDGNode representing the root node of the graph.
Definition: DDG.h:93
llvm::DDGNode::getKind
NodeKind getKind() const
Getter for the kind of this node.
Definition: DDG.h:75
llvm::SimpleDDGNode::classof
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:141
llvm::DDGEdge::operator=
DDGEdge & operator=(DDGEdge &&E)
Definition: DDG.h:230
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::GraphTraits< DataDependenceGraph * >::nodes_begin
static nodes_iterator nodes_begin(DataDependenceGraph *DG)
Definition: DDG.h:520
llvm::GraphTraits< const DataDependenceGraph * >::nodes_iterator
DataDependenceGraph::const_iterator nodes_iterator
Definition: DDG.h:557
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:363
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:265
llvm::DDGNode::~DDGNode
virtual ~DDGNode()=0
llvm::DDGEdge::DDGEdge
DDGEdge(DDGNode &N, EdgeKind K)
Definition: DDG.h:225
llvm::SimpleDDGNode::operator=
SimpleDDGNode & operator=(const SimpleDDGNode &N)=default
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
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:291
llvm::DDGBuilder::shouldCreatePiBlocks
bool shouldCreatePiBlocks() const final override
Definition: DDG.cpp:301
llvm::SimpleDDGNode::~SimpleDDGNode
~SimpleDDGNode()
Definition: DDG.cpp:127
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:632
llvm::SmallVector< DDGNode *, 4 >
llvm::DDGBuilder::createRootNode
DDGNode & createRootNode() final override
Create the root node of the graph.
Definition: DDG.h:351
llvm::DDGNode::operator=
DDGNode & operator=(DDGNode &&N)
Definition: DDG.h:68
llvm::DDGEdge::getKind
EdgeKind getKind() const
Get the edge kind.
Definition: DDG.h:237
llvm::DGNode
Represent a node in the directed graph.
Definition: DirectedGraph.h:73
llvm::GraphTraits< const DDGNode * >::ChildEdgeIteratorType
DDGNode::const_iterator ChildEdgeIteratorType
Definition: DDG.h:538
llvm::GraphTraits< const DDGNode * >::DDGGetTargetNode
static const DDGNode * DDGGetTargetNode(const DGEdge< DDGNode, DDGEdge > *P)
Definition: DDG.h:530
llvm::GraphTraits< DDGNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: DDG.h:500
llvm::SimpleDDGNode::SimpleDDGNode
SimpleDDGNode()=delete
llvm::DirectedGraph::begin
const_iterator begin() const
Definition: DirectedGraph.h:195
llvm::interleaveComma
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
Definition: STLExtras.h:1907
llvm::PiBlockDDGNode::~PiBlockDDGNode
~PiBlockDDGNode()
Definition: DDG.cpp:150
llvm::DDGNode::DDGNode
DDGNode(const NodeKind K)
Definition: DDG.h:57
DenseMap.h
llvm::GraphTraits< const DataDependenceGraph * >::nodes_end
static nodes_iterator nodes_end(const DataDependenceGraph *DG)
Definition: DDG.h:564
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
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:441
llvm::mapped_iterator
Definition: STLExtras.h:298
llvm::GraphTraits< DataDependenceGraph * >::getEntryNode
static NodeRef getEntryNode(DataDependenceGraph *DG)
Definition: DDG.h:517
llvm::PiBlockDDGNode::PiNodeList
SmallVector< DDGNode *, 4 > PiNodeList
Definition: DDG.h:172
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:464
llvm::DataDependenceGraph::~DataDependenceGraph
~DataDependenceGraph()
Definition: DDG.cpp:212
llvm::DDGEdge::DDGEdge
DDGEdge(DDGNode &N)=delete
llvm::GraphTraits< const DDGNode * >::child_edge_end
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: DDG.h:551
llvm::DDGEdge::isMemoryDependence
bool isMemoryDependence() const
Return true if this is a memory dependence edge, and false otherwise.
Definition: DDG.h:243
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::DataDependenceGraph::DataDependenceGraph
DataDependenceGraph(DataDependenceGraph &&G)
Definition: DDG.h:316
llvm::GraphTraits< const DDGNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: DDG.h:540
LoopAnalysisManager.h
llvm::DDGBuilder::createRootedEdge
DDGEdge & createRootedEdge(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.h:381
llvm::DependenceGraphInfo::DependenceGraphInfo
DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
Definition: DDG.h:261
DependenceGraphBuilder.h
DirectedGraph.h
llvm::DDGEdge::operator=
DDGEdge & operator=(const DDGEdge &E)=default
llvm::DirectedGraph::const_iterator
typename NodeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:179
llvm::DDGNode::DDGNode
DDGNode(DDGNode &&N)
Definition: DDG.h:59
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::PiBlockDDGNode::getNodes
const PiNodeList & getNodes() const
Get the list of nodes in this pi-block.
Definition: DDG.h:189
llvm::DDGEdge
Data Dependency Graph Edge.
Definition: DDG.h:213
llvm::SimpleDDGNode::operator=
SimpleDDGNode & operator=(SimpleDDGNode &&N)
Definition: DDG.h:120
llvm::GraphTraits< const DataDependenceGraph * >::nodes_begin
static nodes_iterator nodes_begin(const DataDependenceGraph *DG)
Definition: DDG.h:561
llvm::DependenceGraphInfo::getRoot
NodeType & getRoot() const
Return the root node of the graph.
Definition: DDG.h:271
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:486
llvm::DDGBuilder::createMemoryEdge
DDGEdge & createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.h:375
llvm::SimpleDDGNode::classof
static bool classof(const SimpleDDGNode *N)
Definition: DDG.h:145
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:42
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::PiBlockDDGNode::classof
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:199
llvm::DirectedGraph::iterator
typename NodeListTy::iterator iterator
Definition: DirectedGraph.h:178
llvm::GraphTraits< DDGNode * >::child_edge_end
static ChildEdgeIteratorType child_edge_end(NodeRef N)
Definition: DDG.h:511
llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
llvm::DirectedGraph::end
const_iterator end() const
Definition: DirectedGraph.h:196
llvm::PiBlockDDGNode::PiBlockDDGNode
PiBlockDDGNode()=delete
llvm::DDGAnalysisPrinterPass::DDGAnalysisPrinterPass
DDGAnalysisPrinterPass(raw_ostream &OS)
Definition: DDG.h:428
llvm::DataDependenceGraph::DataDependenceGraph
DataDependenceGraph()=delete
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:101
llvm::GraphTraits< const DDGNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: DDG.h:541
llvm::GraphTraits< DDGNode * >::DDGGetTargetNode
static DDGNode * DDGGetTargetNode(DGEdge< DDGNode, DDGEdge > *P)
Definition: DDG.h:490
llvm::GraphTraits< const DataDependenceGraph * >::getEntryNode
static NodeRef getEntryNode(const DataDependenceGraph *DG)
Definition: DDG.h:558
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::DirectedGraph
Directed graph.
Definition: DirectedGraph.h:173
llvm::PiBlockDDGNode
Subclass of DDGNode representing a pi-block.
Definition: DDG.h:170
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::DependenceInfo
DependenceInfo - This class is the main dependence-analysis driver.
Definition: DependenceAnalysis.h:269
llvm::DDGNode::NodeKind::PiBlock
@ PiBlock
llvm::PiBlockDDGNode::operator=
PiBlockDDGNode & operator=(const PiBlockDDGNode &N)=default
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:220
llvm::GraphTraits< const DDGNode * >
const versions of the grapth trait specializations for DDG
Definition: DDG.h:527
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:262
llvm::SimpleDDGNode
Subclass of DDGNode representing single or multi-instruction nodes.
Definition: DDG.h:108
const
aarch64 promote const
Definition: AArch64PromoteConstant.cpp:232
llvm::GraphTraits< DDGNode * >::child_edge_begin
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: DDG.h:508
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:257
llvm::RootDDGNode::RootDDGNode
RootDDGNode()
Definition: DDG.h:95
llvm::DenseMap< const NodeType *, const PiBlockDDGNode * >
llvm::DDGEdge::DDGEdge
DDGEdge(DDGEdge &&E)
Definition: DDG.h:227
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::GraphTraits< DDGNode * >::ChildEdgeIteratorType
DDGNode::iterator ChildEdgeIteratorType
Definition: DDG.h:498
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::DGNode::operator=
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &N)
Definition: DirectedGraph.h:86
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:1675
llvm::DDGBuilder::createDefUseEdge
DDGEdge & createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.h:369
llvm::DataDependenceGraph::NodeType
DDGNode NodeType
Definition: DDG.h:311
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:268
llvm::GraphTraits< DataDependenceGraph * >::nodes_iterator
DataDependenceGraph::iterator nodes_iterator
Definition: DDG.h:516
llvm::DDGAnalysisPrinterPass
Textual printer pass for the DDG of a loop.
Definition: DDG.h:426
llvm::DDGEdge::isDefUse
bool isDefUse() const
Return true if this is a def-use edge, and false otherwise.
Definition: DDG.h:240
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::DDGNode::NodeKind::Root
@ Root
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:247
llvm::LoopInfo
Definition: LoopInfo.h:1102
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:1823
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:38
llvm::GraphTraits< DataDependenceGraph * >::nodes_end
static nodes_iterator nodes_end(DataDependenceGraph *DG)
Definition: DDG.h:523
llvm::DGNode::const_iterator
typename EdgeListTy::const_iterator const_iterator
Definition: DirectedGraph.h:77
llvm::RootDDGNode::RootDDGNode
RootDDGNode(RootDDGNode &&N)
Definition: DDG.h:97
llvm::SimpleDDGNode::getInstructions
InstructionListType & getInstructions()
Definition: DDG.h:131
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:266
llvm::DependenceGraphInfo::Root
NodeType * Root
Definition: DDG.h:300
NodeKind
Determine the kind of a node from its type.
Definition: ItaniumDemangle.h:2360
llvm::DDGBuilder::createFineGrainedNode
DDGNode & createFineGrainedNode(Instruction &I) final override
Create an atomic node in the graph given a single instruction.
Definition: DDG.h:357
std
Definition: BitVector.h:851
llvm::RootDDGNode::classof
static bool classof(const RootDDGNode *N)
Definition: DDG.h:104
llvm::SimpleDDGNode::getLastInstruction
Instruction * getLastInstruction() const
Definition: DDG.h:138
llvm::DDGEdge::DDGEdge
DDGEdge(const DDGEdge &E)
Definition: DDG.h:226
llvm::DependenceGraphInfo::~DependenceGraphInfo
virtual ~DependenceGraphInfo()=default
llvm::DDGNode::NodeKind::MultiInstruction
@ MultiInstruction
llvm::GraphTraits< const DDGNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: DDG.h:544
llvm::DependenceGraphInfo::DependenceGraphInfo
DependenceGraphInfo(DependenceGraphInfo &&G)
Definition: DDG.h:263
llvm::DDGEdge::EdgeKind::Unknown
@ Unknown
llvm::PiBlockDDGNode::operator=
PiBlockDDGNode & operator=(PiBlockDDGNode &&N)
Definition: DDG.h:182
llvm::GraphTraits< DDGNode * >
non-const versions of the grapth trait specializations for DDG
Definition: DDG.h:487
llvm::DependenceGraphInfo::DI
const DependenceInfo DI
Definition: DDG.h:296
llvm::PiBlockDDGNode::getNodes
PiNodeList & getNodes()
Definition: DDG.h:193
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:3527
llvm::GraphTraits< DDGNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: DDG.h:501
llvm::DDGNode
Data Dependence Graph Node The graph can represent the following types of nodes:
Definition: DDG.h:44
llvm::DGEdge::operator=
DGEdge< NodeType, EdgeType > & operator=(const DGEdge< NodeType, EdgeType > &E)
Definition: DirectedGraph.h:35
N
#define N
llvm::DGNode::iterator
typename EdgeListTy::iterator iterator
Definition: DirectedGraph.h:76
llvm::DataDependenceGraph
Data Dependency Graph.
Definition: DDG.h:306
llvm::DDGBuilder::getNodesInPiBlock
const NodeListType & getNodesInPiBlock(const DDGNode &N) final override
Definition: DDG.h:389
llvm::SmallVectorImpl< Instruction * >
llvm::SimpleDDGNode::getFirstInstruction
Instruction * getFirstInstruction() const
Get the first/last instruction in the node.
Definition: DDG.h:137
llvm::DDGEdge::EdgeKind::MemoryDependence
@ MemoryDependence
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::DDGBuilder::shouldSimplify
bool shouldSimplify() const final override
Definition: DDG.cpp:299
InstructionListType
SmallVector< Instruction *, 2 > InstructionListType
Definition: DependenceGraphBuilder.cpp:35
llvm::DDGNode::setKind
void setKind(NodeKind K)
Setter for the kind of this node.
Definition: DDG.h:85
llvm::DGEdge
Represent an edge in the directed graph.
Definition: DirectedGraph.h:28
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:37
DependenceAnalysis.h
llvm::DDGAnalysis
Analysis pass that builds the DDG for a loop.
Definition: DDG.h:415
llvm::DDGAnalysis::Result
std::unique_ptr< DataDependenceGraph > Result
Definition: DDG.h:417
llvm::DDGBuilder
Concrete implementation of a pure data dependence graph builder.
Definition: DDG.h:346
llvm::GraphTraits< DDGNode * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: DDG.h:504
llvm::raw_string_ostream::str
std::string & str()
Returns the string's reference.
Definition: raw_ostream.h:650
llvm::DDGNode::NodeKind::Unknown
@ Unknown
llvm::DDGNode::operator=
DDGNode & operator=(const DDGNode &N)
Definition: DDG.h:62
llvm::DDGBuilder::mergeNodes
void mergeNodes(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.cpp:279
llvm::GraphTraits< const DDGNode * >::child_edge_begin
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: DDG.h:548
llvm::RootDDGNode::~RootDDGNode
~RootDDGNode()=default
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:243
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::DependenceGraphInfo::DependenceGraphInfo
DependenceGraphInfo()=delete
llvm::DDGEdge::EdgeKind
EdgeKind
The kind of edge in the DDG.
Definition: DDG.h:216
llvm::SimpleDDGNode::getInstructions
const InstructionListType & getInstructions() const
Get the list of instructions in this node.
Definition: DDG.h:127
llvm::RootDDGNode::classof
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
Definition: DDG.h:101
llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph
DataDependenceGraph & Graph
Reference to the graph that gets built by a concrete implementation of this builder.
Definition: DependenceGraphBuilder.h:180