LLVM  16.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)
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 {
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  }
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  }
377  assert(E && "Failed to allocate memory for edge");
378  Graph.connect(Src, Tgt, *E);
379  return *E;
380  }
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 {
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, const DDGNode &Tgt) const final;
398  void mergeNodes(DDGNode &Src, DDGNode &Tgt) final;
399  bool shouldSimplify() const final;
400  bool shouldCreatePiBlocks() const final;
401 };
402 
403 raw_ostream &operator<<(raw_ostream &OS, const DDGNode &N);
404 raw_ostream &operator<<(raw_ostream &OS, const DDGNode::NodeKind K);
405 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge &E);
406 raw_ostream &operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K);
408 
409 //===--------------------------------------------------------------------===//
410 // DDG Analysis Passes
411 //===--------------------------------------------------------------------===//
412 
413 /// Analysis pass that builds the DDG for a loop.
415 public:
416  using Result = std::unique_ptr<DataDependenceGraph>;
418 
419 private:
421  static AnalysisKey Key;
422 };
423 
424 /// Textual printer pass for the DDG of a loop.
425 class DDGAnalysisPrinterPass : public PassInfoMixin<DDGAnalysisPrinterPass> {
426 public:
427  explicit DDGAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
430 
431 private:
432  raw_ostream &OS;
433 };
434 
435 //===--------------------------------------------------------------------===//
436 // DependenceGraphInfo Implementation
437 //===--------------------------------------------------------------------===//
438 
439 template <typename NodeType>
441  const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const {
442  assert(Deps.empty() && "Expected empty output list at the start.");
443 
444  // List of memory access instructions from src and dst nodes.
445  SmallVector<Instruction *, 8> SrcIList, DstIList;
446  auto isMemoryAccess = [](const Instruction *I) {
447  return I->mayReadOrWriteMemory();
448  };
449  Src.collectInstructions(isMemoryAccess, SrcIList);
450  Dst.collectInstructions(isMemoryAccess, DstIList);
451 
452  for (auto *SrcI : SrcIList)
453  for (auto *DstI : DstIList)
454  if (auto Dep =
455  const_cast<DependenceInfo *>(&DI)->depends(SrcI, DstI, true))
456  Deps.push_back(std::move(Dep));
457 
458  return !Deps.empty();
459 }
460 
461 template <typename NodeType>
462 std::string
464  const NodeType &Dst) const {
465  std::string Str;
466  raw_string_ostream OS(Str);
467  DependenceList Deps;
468  if (!getDependencies(Src, Dst, Deps))
469  return OS.str();
470  interleaveComma(Deps, OS, [&](const std::unique_ptr<Dependence> &D) {
471  D->dump(OS);
472  // Remove the extra new-line character printed by the dump
473  // method
474  if (OS.str().back() == '\n')
475  OS.str().pop_back();
476  });
477 
478  return OS.str();
479 }
480 
481 //===--------------------------------------------------------------------===//
482 // GraphTraits specializations for the DDG
483 //===--------------------------------------------------------------------===//
484 
485 /// non-const versions of the grapth trait specializations for DDG
486 template <> struct GraphTraits<DDGNode *> {
487  using NodeRef = DDGNode *;
488 
490  return &P->getTargetNode();
491  }
492 
493  // Provide a mapped iterator so that the GraphTrait-based implementations can
494  // find the target nodes without having to explicitly go through the edges.
495  using ChildIteratorType =
496  mapped_iterator<DDGNode::iterator, decltype(&DDGGetTargetNode)>;
498 
499  static NodeRef getEntryNode(NodeRef N) { return N; }
501  return ChildIteratorType(N->begin(), &DDGGetTargetNode);
502  }
504  return ChildIteratorType(N->end(), &DDGGetTargetNode);
505  }
506 
508  return N->begin();
509  }
510  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
511 };
512 
513 template <>
517  return &DG->getRoot();
518  }
520  return DG->begin();
521  }
522  static nodes_iterator nodes_end(DataDependenceGraph *DG) { return DG->end(); }
523 };
524 
525 /// const versions of the grapth trait specializations for DDG
526 template <> struct GraphTraits<const DDGNode *> {
527  using NodeRef = const DDGNode *;
528 
530  return &P->getTargetNode();
531  }
532 
533  // Provide a mapped iterator so that the GraphTrait-based implementations can
534  // find the target nodes without having to explicitly go through the edges.
535  using ChildIteratorType =
536  mapped_iterator<DDGNode::const_iterator, decltype(&DDGGetTargetNode)>;
538 
539  static NodeRef getEntryNode(NodeRef N) { return N; }
541  return ChildIteratorType(N->begin(), &DDGGetTargetNode);
542  }
544  return ChildIteratorType(N->end(), &DDGGetTargetNode);
545  }
546 
548  return N->begin();
549  }
550  static ChildEdgeIteratorType child_edge_end(NodeRef N) { return N->end(); }
551 };
552 
553 template <>
558  return &DG->getRoot();
559  }
561  return DG->begin();
562  }
564  return DG->end();
565  }
566 };
567 
568 } // namespace llvm
569 
570 #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:18
llvm::GraphTraits< DataDependenceGraph * >::nodes_begin
static nodes_iterator nodes_begin(DataDependenceGraph *DG)
Definition: DDG.h:519
llvm::GraphTraits< const DataDependenceGraph * >::nodes_iterator
DataDependenceGraph::const_iterator nodes_iterator
Definition: DDG.h:556
llvm::DDGEdge::EdgeKind::Rooted
@ Rooted
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::SimpleDDGNode::~SimpleDDGNode
~SimpleDDGNode()
Definition: DDG.cpp:127
llvm::raw_string_ostream
A raw_ostream that writes to an std::string.
Definition: raw_ostream.h:628
llvm::SmallVector< DDGNode *, 4 >
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:537
llvm::GraphTraits< const DDGNode * >::DDGGetTargetNode
static const DDGNode * DDGGetTargetNode(const DGEdge< DDGNode, DDGEdge > *P)
Definition: DDG.h:529
llvm::GraphTraits< DDGNode * >::getEntryNode
static NodeRef getEntryNode(NodeRef N)
Definition: DDG.h:499
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:1902
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:563
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:440
llvm::mapped_iterator
Definition: STLExtras.h:286
llvm::DDGBuilder::getNodesInPiBlock
const NodeListType & getNodesInPiBlock(const DDGNode &N) final
Definition: DDG.h:389
llvm::GraphTraits< DataDependenceGraph * >::getEntryNode
static NodeRef getEntryNode(DataDependenceGraph *DG)
Definition: DDG.h:516
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:463
llvm::DDGBuilder::createRootedEdge
DDGEdge & createRootedEdge(DDGNode &Src, DDGNode &Tgt) final
Definition: DDG.h:381
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:550
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:539
LoopAnalysisManager.h
llvm::DependenceGraphInfo::DependenceGraphInfo
DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
Definition: DDG.h:261
DependenceGraphBuilder.h
llvm::DDGBuilder::createPiBlock
DDGNode & createPiBlock(const NodeListType &L) final
Create a pi-block node in the graph representing a group of nodes in an SCC of the graph.
Definition: DDG.h:363
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:560
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::DDGBuilder::areNodesMergeable
bool areNodesMergeable(const DDGNode &Src, const DDGNode &Tgt) const final
Return true if the two nodes \pSrc and \pTgt are both simple nodes and the consecutive instructions a...
Definition: DDG.cpp:266
llvm::DDGEdge::EdgeKind::RegisterDefUse
@ RegisterDefUse
llvm::AMDGPU::PALMD::Key
Key
PAL metadata keys.
Definition: AMDGPUMetadata.h:486
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:52
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:510
llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >
llvm::DirectedGraph::end
const_iterator end() const
Definition: DirectedGraph.h:196
llvm::PiBlockDDGNode::PiBlockDDGNode
PiBlockDDGNode()=delete
llvm::DDGBuilder::createRootNode
DDGNode & createRootNode() final
Create the root node of the graph.
Definition: DDG.h:351
llvm::DDGAnalysisPrinterPass::DDGAnalysisPrinterPass
DDGAnalysisPrinterPass(raw_ostream &OS)
Definition: DDG.h:427
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:540
llvm::GraphTraits< DDGNode * >::DDGGetTargetNode
static DDGNode * DDGGetTargetNode(DGEdge< DDGNode, DDGEdge > *P)
Definition: DDG.h:489
llvm::GraphTraits< const DataDependenceGraph * >::getEntryNode
static NodeRef getEntryNode(const DataDependenceGraph *DG)
Definition: DDG.h:557
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:291
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:526
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:507
llvm::DDGBuilder::shouldSimplify
bool shouldSimplify() const final
Definition: DDG.cpp:299
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:497
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:1666
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:515
llvm::DDGAnalysisPrinterPass
Textual printer pass for the DDG of a loop.
Definition: DDG.h:425
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:1105
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1818
llvm::DDGBuilder::createFineGrainedNode
DDGNode & createFineGrainedNode(Instruction &I) final
Create an atomic node in the graph given a single instruction.
Definition: DDG.h:357
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:522
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::createDefUseEdge
DDGEdge & createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final
Definition: DDG.h:369
llvm::DependenceGraphInfo::Root
NodeType * Root
Definition: DDG.h:300
llvm::DDGBuilder::shouldCreatePiBlocks
bool shouldCreatePiBlocks() const final
Definition: DDG.cpp:301
NodeKind
Determine the kind of a node from its type.
Definition: ItaniumDemangle.h:2372
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:543
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::DDGBuilder::createMemoryEdge
DDGEdge & createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final
Definition: DDG.h:375
llvm::DDGBuilder::mergeNodes
void mergeNodes(DDGNode &Src, DDGNode &Tgt) final
Definition: DDG.cpp:279
llvm::GraphTraits< DDGNode * >
non-const versions of the grapth trait specializations for DDG
Definition: DDG.h:486
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:3590
llvm::GraphTraits< DDGNode * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: DDG.h:500
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::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
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:414
llvm::DDGAnalysis::Result
std::unique_ptr< DataDependenceGraph > Result
Definition: DDG.h:416
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:503
llvm::raw_string_ostream::str
std::string & str()
Returns the string's reference.
Definition: raw_ostream.h:646
llvm::DDGNode::NodeKind::Unknown
@ Unknown
llvm::DDGNode::operator=
DDGNode & operator=(const DDGNode &N)
Definition: DDG.h:62
llvm::GraphTraits< const DDGNode * >::child_edge_begin
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
Definition: DDG.h:547
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