LLVM  10.0.0svn
DDG.cpp
Go to the documentation of this file.
1 //===- DDG.cpp - Data Dependence Graph -------------------------------------==//
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 // The implementation for the data dependence graph.
10 //===----------------------------------------------------------------------===//
11 #include "llvm/Analysis/DDG.h"
12 #include "llvm/Analysis/LoopInfo.h"
13 
14 using namespace llvm;
15 
16 #define DEBUG_TYPE "ddg"
17 
18 template class llvm::DGEdge<DDGNode, DDGEdge>;
19 template class llvm::DGNode<DDGNode, DDGEdge>;
21 
22 //===--------------------------------------------------------------------===//
23 // DDGNode implementation
24 //===--------------------------------------------------------------------===//
26 
28  llvm::function_ref<bool(Instruction *)> const &Pred,
29  InstructionListType &IList) const {
30  assert(IList.empty() && "Expected the IList to be empty on entry.");
31  if (isa<SimpleDDGNode>(this)) {
32  for (auto *I : cast<const SimpleDDGNode>(this)->getInstructions())
33  if (Pred(I))
34  IList.push_back(I);
35  } else
36  llvm_unreachable("unimplemented type of node");
37  return !IList.empty();
38 }
39 
41  const char *Out;
42  switch (K) {
44  Out = "single-instruction";
45  break;
47  Out = "multi-instruction";
48  break;
50  Out = "root";
51  break;
53  Out = "??";
54  break;
55  }
56  OS << Out;
57  return OS;
58 }
59 
61  OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
62  if (isa<SimpleDDGNode>(N)) {
63  OS << " Instructions:\n";
64  for (auto *I : cast<const SimpleDDGNode>(N).getInstructions())
65  OS.indent(2) << *I << "\n";
66  } else if (!isa<RootDDGNode>(N))
67  llvm_unreachable("unimplemented type of node");
68 
69  OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
70  for (auto &E : N.getEdges())
71  OS.indent(2) << *E;
72  return OS;
73 }
74 
75 //===--------------------------------------------------------------------===//
76 // SimpleDDGNode implementation
77 //===--------------------------------------------------------------------===//
78 
80  : DDGNode(NodeKind::SingleInstruction), InstList() {
81  assert(InstList.empty() && "Expected empty list.");
82  InstList.push_back(&I);
83 }
84 
86  : DDGNode(N), InstList(N.InstList) {
87  assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
88  (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
89  "constructing from invalid simple node.");
90 }
91 
93  : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {
94  assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
95  (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
96  "constructing from invalid simple node.");
97 }
98 
99 SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
100 
101 //===--------------------------------------------------------------------===//
102 // DDGEdge implementation
103 //===--------------------------------------------------------------------===//
104 
106  const char *Out;
107  switch (K) {
109  Out = "def-use";
110  break;
112  Out = "memory";
113  break;
115  Out = "rooted";
116  break;
118  Out = "??";
119  break;
120  }
121  OS << Out;
122  return OS;
123 }
124 
126  OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
127  return OS;
128 }
129 
130 //===--------------------------------------------------------------------===//
131 // DataDependenceGraph implementation
132 //===--------------------------------------------------------------------===//
134 
136  : DependenceGraphInfo(F.getName().str(), D) {
137  BasicBlockListType BBList;
138  for (auto &BB : F.getBasicBlockList())
139  BBList.push_back(&BB);
140  DDGBuilder(*this, D, BBList).populate();
141 }
142 
144  : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
145  L.getHeader()->getName())
146  .str(),
147  D) {
148  BasicBlockListType BBList;
149  for (BasicBlock *BB : L.blocks())
150  BBList.push_back(BB);
151  DDGBuilder(*this, D, BBList).populate();
152 }
153 
155  for (auto *N : Nodes) {
156  for (auto *E : *N)
157  delete E;
158  delete N;
159  }
160 }
161 
163  if (!DDGBase::addNode(N))
164  return false;
165 
166  // In general, if the root node is already created and linked, it is not safe
167  // to add new nodes since they may be unreachable by the root.
168  // TODO: Allow adding Pi-block nodes after root is created. Pi-blocks are an
169  // exception because they represent components that are already reachable by
170  // root.
171  assert(!Root && "Root node is already added. No more nodes can be added.");
172  if (isa<RootDDGNode>(N))
173  Root = &N;
174 
175  return true;
176 }
177 
179  for (auto *Node : G)
180  OS << *Node << "\n";
181  return OS;
182 }
183 
184 //===--------------------------------------------------------------------===//
185 // DDG Analysis Passes
186 //===--------------------------------------------------------------------===//
187 
188 /// DDG as a loop pass.
191  Function *F = L.getHeader()->getParent();
192  DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
193  return std::make_unique<DataDependenceGraph>(L, DI);
194 }
195 AnalysisKey DDGAnalysis::Key;
196 
199  LPMUpdater &U) {
200  OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
201  OS << *AM.getResult<DDGAnalysis>(L, AR);
202  return PreservedAnalyses::all();
203 }
Data Dependency Graph.
Definition: DDG.h:242
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:777
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Data Dependency Graph Edge.
Definition: DDG.h:163
Data Dependence Graph Node The graph can represent the following types of nodes:
Definition: DDG.h:38
void push_back(const T &Elt)
Definition: SmallVector.h:211
const NodeType & getTargetNode() const
Retrieve the target node this edge connects to.
Definition: DirectedGraph.h:45
raw_ostream & indent(unsigned NumSpaces)
indent - Insert &#39;NumSpaces&#39; spaces.
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:104
virtual ~DDGNode()=0
Definition: DDG.cpp:25
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
F(f)
DependenceInfo - This class is the main dependence-analysis driver.
Definition: BitVector.h:937
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
static StringRef getName(Value *V)
BlockT * getHeader() const
Definition: LoopInfo.h:105
const EdgeListTy & getEdges() const
Retrieve the outgoing edges for the node.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: DDG.cpp:197
EdgeKind getKind() const
Get the edge kind.
Definition: DDG.h:185
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
NodeType * Root
Definition: DDG.h:236
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
Represent an edge in the directed graph.
Definition: DirectedGraph.h:27
EdgeKind
The kind of edge in the DDG.
Definition: DDG.h:166
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const StringRef getName() const
Return the label that is used to name this graph.
Definition: DDG.h:216
NodeKind getKind() const
Getter for the kind of this node.
Definition: DDG.h:68
Determine the kind of a node from its type.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
bool addNode(NodeType &N)
Add node N to the graph, if it&#39;s not added yet, and keep track of the root node.
Definition: DDG.cpp:162
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
std::unique_ptr< DataDependenceGraph > Result
Definition: DDG.h:322
Directed graph.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Definition: DDG.h:203
Represent a node in the directed graph.
Definition: DirectedGraph.h:67
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
friend class DDGBuilder
Definition: DDG.h:243
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
DDG as a loop pass.
Definition: DDG.cpp:189
const DependenceInfo DI
Definition: DDG.h:232
Analysis pass that builds the DDG for a loop.
Definition: DDG.h:320
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
const BasicBlockListType & getBasicBlockList() const
Get the underlying elements of the Function...
Definition: Function.h:662
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2047
Subclass of DDGNode representing single or multi-instruction nodes.
Definition: DDG.h:101
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool addNode(NodeType &N)
Add the given node N to the graph if it is not already present.
static const Function * getParent(const Value *V)
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
A container for analyses that lazily runs them and caches their results.
iterator_range< block_iterator > blocks() const
Definition: LoopInfo.h:161
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:71
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:27