LLVM  13.0.0git
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/ADT/SCCIterator.h"
13 #include "llvm/Analysis/LoopInfo.h"
16 
17 using namespace llvm;
18 
20  "ddg-simplify", cl::init(true), cl::Hidden, cl::ZeroOrMore,
21  cl::desc(
22  "Simplify DDG by merging nodes that have less interesting edges."));
23 
24 static cl::opt<bool>
25  CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::ZeroOrMore,
26  cl::desc("Create pi-block nodes."));
27 
28 #define DEBUG_TYPE "ddg"
29 
30 template class llvm::DGEdge<DDGNode, DDGEdge>;
31 template class llvm::DGNode<DDGNode, DDGEdge>;
33 
34 //===--------------------------------------------------------------------===//
35 // DDGNode implementation
36 //===--------------------------------------------------------------------===//
38 
40  llvm::function_ref<bool(Instruction *)> const &Pred,
41  InstructionListType &IList) const {
42  assert(IList.empty() && "Expected the IList to be empty on entry.");
43  if (isa<SimpleDDGNode>(this)) {
44  for (Instruction *I : cast<const SimpleDDGNode>(this)->getInstructions())
45  if (Pred(I))
46  IList.push_back(I);
47  } else if (isa<PiBlockDDGNode>(this)) {
48  for (const DDGNode *PN : cast<const PiBlockDDGNode>(this)->getNodes()) {
49  assert(!isa<PiBlockDDGNode>(PN) && "Nested PiBlocks are not supported.");
51  PN->collectInstructions(Pred, TmpIList);
52  llvm::append_range(IList, TmpIList);
53  }
54  } else
55  llvm_unreachable("unimplemented type of node");
56  return !IList.empty();
57 }
58 
60  const char *Out;
61  switch (K) {
63  Out = "single-instruction";
64  break;
66  Out = "multi-instruction";
67  break;
69  Out = "pi-block";
70  break;
72  Out = "root";
73  break;
75  Out = "?? (error)";
76  break;
77  }
78  OS << Out;
79  return OS;
80 }
81 
83  OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
84  if (isa<SimpleDDGNode>(N)) {
85  OS << " Instructions:\n";
86  for (const Instruction *I : cast<const SimpleDDGNode>(N).getInstructions())
87  OS.indent(2) << *I << "\n";
88  } else if (isa<PiBlockDDGNode>(&N)) {
89  OS << "--- start of nodes in pi-block ---\n";
90  auto &Nodes = cast<const PiBlockDDGNode>(&N)->getNodes();
91  unsigned Count = 0;
92  for (const DDGNode *N : Nodes)
93  OS << *N << (++Count == Nodes.size() ? "" : "\n");
94  OS << "--- end of nodes in pi-block ---\n";
95  } else if (!isa<RootDDGNode>(N))
96  llvm_unreachable("unimplemented type of node");
97 
98  OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
99  for (auto &E : N.getEdges())
100  OS.indent(2) << *E;
101  return OS;
102 }
103 
104 //===--------------------------------------------------------------------===//
105 // SimpleDDGNode implementation
106 //===--------------------------------------------------------------------===//
107 
109  : DDGNode(NodeKind::SingleInstruction), InstList() {
110  assert(InstList.empty() && "Expected empty list.");
111  InstList.push_back(&I);
112 }
113 
115  : DDGNode(N), InstList(N.InstList) {
116  assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
117  (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
118  "constructing from invalid simple node.");
119 }
120 
122  : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {
123  assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
124  (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
125  "constructing from invalid simple node.");
126 }
127 
128 SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
129 
130 //===--------------------------------------------------------------------===//
131 // PiBlockDDGNode implementation
132 //===--------------------------------------------------------------------===//
133 
135  : DDGNode(NodeKind::PiBlock), NodeList(List) {
136  assert(!NodeList.empty() && "pi-block node constructed with an empty list.");
137 }
138 
140  : DDGNode(N), NodeList(N.NodeList) {
141  assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
142  "constructing from invalid pi-block node.");
143 }
144 
146  : DDGNode(std::move(N)), NodeList(std::move(N.NodeList)) {
147  assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
148  "constructing from invalid pi-block node.");
149 }
150 
152 
153 //===--------------------------------------------------------------------===//
154 // DDGEdge implementation
155 //===--------------------------------------------------------------------===//
156 
158  const char *Out;
159  switch (K) {
161  Out = "def-use";
162  break;
164  Out = "memory";
165  break;
167  Out = "rooted";
168  break;
170  Out = "?? (error)";
171  break;
172  }
173  OS << Out;
174  return OS;
175 }
176 
178  OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
179  return OS;
180 }
181 
182 //===--------------------------------------------------------------------===//
183 // DataDependenceGraph implementation
184 //===--------------------------------------------------------------------===//
186 
188  : DependenceGraphInfo(F.getName().str(), D) {
189  // Put the basic blocks in program order for correct dependence
190  // directions.
191  BasicBlockListType BBList;
192  for (auto &SCC : make_range(scc_begin(&F), scc_end(&F)))
193  append_range(BBList, SCC);
194  std::reverse(BBList.begin(), BBList.end());
195  DDGBuilder(*this, D, BBList).populate();
196 }
197 
199  DependenceInfo &D)
200  : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
201  L.getHeader()->getName())
202  .str(),
203  D) {
204  // Put the basic blocks in program order for correct dependence
205  // directions.
206  LoopBlocksDFS DFS(&L);
207  DFS.perform(&LI);
208  BasicBlockListType BBList;
209  append_range(BBList, make_range(DFS.beginRPO(), DFS.endRPO()));
210  DDGBuilder(*this, D, BBList).populate();
211 }
212 
214  for (auto *N : Nodes) {
215  for (auto *E : *N)
216  delete E;
217  delete N;
218  }
219 }
220 
222  if (!DDGBase::addNode(N))
223  return false;
224 
225  // In general, if the root node is already created and linked, it is not safe
226  // to add new nodes since they may be unreachable by the root. However,
227  // pi-block nodes need to be added after the root node is linked, and they are
228  // always reachable by the root, because they represent components that are
229  // already reachable by root.
230  auto *Pi = dyn_cast<PiBlockDDGNode>(&N);
231  assert((!Root || Pi) &&
232  "Root node is already added. No more nodes can be added.");
233 
234  if (isa<RootDDGNode>(N))
235  Root = &N;
236 
237  if (Pi)
238  for (DDGNode *NI : Pi->getNodes())
239  PiBlockMap.insert(std::make_pair(NI, Pi));
240 
241  return true;
242 }
243 
245  if (PiBlockMap.find(&N) == PiBlockMap.end())
246  return nullptr;
247  auto *Pi = PiBlockMap.find(&N)->second;
248  assert(PiBlockMap.find(Pi) == PiBlockMap.end() &&
249  "Nested pi-blocks detected.");
250  return Pi;
251 }
252 
254  for (DDGNode *Node : G)
255  // Avoid printing nodes that are part of a pi-block twice. They will get
256  // printed when the pi-block is printed.
257  if (!G.getPiBlock(*Node))
258  OS << *Node << "\n";
259  OS << "\n";
260  return OS;
261 }
262 
263 //===--------------------------------------------------------------------===//
264 // DDGBuilder implementation
265 //===--------------------------------------------------------------------===//
266 
268  const DDGNode &Tgt) const {
269  // Only merge two nodes if they are both simple nodes and the consecutive
270  // instructions after merging belong to the same BB.
271  const auto *SimpleSrc = dyn_cast<const SimpleDDGNode>(&Src);
272  const auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(&Tgt);
273  if (!SimpleSrc || !SimpleTgt)
274  return false;
275 
276  return SimpleSrc->getLastInstruction()->getParent() ==
277  SimpleTgt->getFirstInstruction()->getParent();
278 }
279 
281  DDGEdge &EdgeToFold = A.back();
282  assert(A.getEdges().size() == 1 && EdgeToFold.getTargetNode() == B &&
283  "Expected A to have a single edge to B.");
284  assert(isa<SimpleDDGNode>(&A) && isa<SimpleDDGNode>(&B) &&
285  "Expected simple nodes");
286 
287  // Copy instructions from B to the end of A.
288  cast<SimpleDDGNode>(&A)->appendInstructions(*cast<SimpleDDGNode>(&B));
289 
290  // Move to A any outgoing edges from B.
291  for (DDGEdge *BE : B)
292  Graph.connect(A, BE->getTargetNode(), *BE);
293 
294  A.removeEdge(EdgeToFold);
295  destroyEdge(EdgeToFold);
296  Graph.removeNode(B);
297  destroyNode(B);
298 }
299 
300 bool DDGBuilder::shouldSimplify() const { return SimplifyDDG; }
301 
303 
304 //===--------------------------------------------------------------------===//
305 // DDG Analysis Passes
306 //===--------------------------------------------------------------------===//
307 
308 /// DDG as a loop pass.
311  Function *F = L.getHeader()->getParent();
312  DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
313  return std::make_unique<DataDependenceGraph>(L, AR.LI, DI);
314 }
315 AnalysisKey DDGAnalysis::Key;
316 
319  LPMUpdater &U) {
320  OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
321  OS << *AM.getResult<DDGAnalysis>(L, AR);
322  return PreservedAnalyses::all();
323 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::DependenceGraphInfo
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Definition: DDG.h:265
getName
static StringRef getName(Value *V)
Definition: ProvenanceAnalysisEvaluator.cpp:42
llvm::DDGNode::getKind
NodeKind getKind() const
Getter for the kind of this node.
Definition: DDG.h:73
llvm
Definition: AllocatorList.h:23
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
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:264
llvm::DDGNode::~DDGNode
virtual ~DDGNode()=0
Definition: DDG.cpp:37
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
SCCIterator.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::DDGBuilder::shouldCreatePiBlocks
bool shouldCreatePiBlocks() const final override
Definition: DDG.cpp:302
llvm::DDGAnalysis::run
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
DDG as a loop pass.
Definition: DDG.cpp:309
llvm::SimpleDDGNode::~SimpleDDGNode
~SimpleDDGNode()
Definition: DDG.cpp:128
llvm::SmallVector< Instruction *, 8 >
llvm::DGNode
Represent a node in the directed graph.
Definition: DirectedGraph.h:72
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::SimpleDDGNode::SimpleDDGNode
SimpleDDGNode()=delete
llvm::PiBlockDDGNode::~PiBlockDDGNode
~PiBlockDDGNode()
Definition: DDG.cpp:151
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:329
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::DataDependenceGraph::~DataDependenceGraph
~DataDependenceGraph()
Definition: DDG.cpp:213
llvm::LoopBlocksDFS::beginRPO
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
F
#define F(x, y, z)
Definition: MD5.cpp:56
CommandLine.h
llvm::DirectedGraph::Nodes
NodeListTy Nodes
Definition: DirectedGraph.h:274
llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::destroyNode
virtual void destroyNode(NodeType &N)
Deallocate memory of node N.
Definition: DependenceGraphBuilder.h:139
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::DDGEdge
Data Dependency Graph Edge.
Definition: DDG.h:219
llvm::DDGEdge::EdgeKind::RegisterDefUse
@ RegisterDefUse
llvm::DDGNode::NodeKind
NodeKind
Definition: DDG.h:46
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
NodeList
Definition: MicrosoftDemangle.cpp:37
llvm::Instruction
Definition: Instruction.h:45
llvm::LoopBlocksDFS::endRPO
RPOIterator endRPO() const
Definition: LoopIterator.h:140
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::PiBlockDDGNode::PiBlockDDGNode
PiBlockDDGNode()=delete
LoopIterator.h
llvm::DataDependenceGraph::DataDependenceGraph
DataDependenceGraph()=delete
LoopInfo.h
llvm::scc_begin
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:228
llvm::cl::ZeroOrMore
@ ZeroOrMore
Definition: CommandLine.h:120
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::LoopBlocksDFS
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
llvm::PiBlockDDGNode
Subclass of DDGNode representing a pi-block.
Definition: DDG.h:172
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::cl::opt< bool >
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
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:240
llvm::SimpleDDGNode
Subclass of DDGNode representing single or multi-instruction nodes.
Definition: DDG.h:106
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::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::DGEdge::getTargetNode
const NodeType & getTargetNode() const
Retrieve the target node this edge connects to.
Definition: DirectedGraph.h:47
llvm::LoopBlocksDFS::perform
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1149
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:1540
llvm::DDGNode::NodeKind::SingleInstruction
@ SingleInstruction
llvm::DDGNode::NodeKind::Root
@ Root
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:285
DDG.h
llvm::LoopInfo
Definition: LoopInfo.h:1080
llvm::DDGAnalysisPrinterPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: DDG.cpp:317
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:767
CreatePiBlocks
static cl::opt< bool > CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::ZeroOrMore, cl::desc("Create pi-block nodes."))
llvm::append_range
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:1672
llvm::LoopStandardAnalysisResults::LI
LoopInfo & LI
Definition: LoopAnalysisManager.h:56
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::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:294
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
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:2209
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
std
Definition: BitVector.h:838
llvm::DenseMapBase::end
iterator end()
Definition: DenseMap.h:83
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::destroyEdge
virtual void destroyEdge(EdgeType &E)
Deallocate memory of edge E.
Definition: DependenceGraphBuilder.h:136
llvm::DDGNode::NodeKind::MultiInstruction
@ MultiInstruction
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
llvm::DDGEdge::EdgeKind::Unknown
@ Unknown
llvm::DirectedGraph::addNode
bool addNode(NodeType &N)
Add the given node N to the graph if it is not already present.
Definition: DirectedGraph.h:216
llvm::LoopStandardAnalysisResults::SE
ScalarEvolution & SE
Definition: LoopAnalysisManager.h:57
llvm::LoopStandardAnalysisResults::AA
AAResults & AA
Definition: LoopAnalysisManager.h:53
llvm::raw_ostream::indent
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Definition: raw_ostream.cpp:497
llvm::DDGNode
Data Dependence Graph Node The graph can represent the following types of nodes:
Definition: DDG.h:42
List
const NodeList & List
Definition: RDFGraph.cpp:201
N
#define N
llvm::DataDependenceGraph
Data Dependency Graph.
Definition: DDG.h:316
llvm::SmallVectorImpl< Instruction * >
llvm::DirectedGraph::removeNode
bool removeNode(NodeType &N)
Remove the given node N from the graph.
Definition: DirectedGraph.h:242
llvm::DDGEdge::EdgeKind::MemoryDependence
@ MemoryDependence
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::scc_end
scc_iterator< T > scc_end(const T &G)
Construct the end iterator for a deduced graph type T.
Definition: SCCIterator.h:233
llvm::DDGBuilder::shouldSimplify
bool shouldSimplify() const final override
Definition: DDG.cpp:300
llvm::DGEdge
Represent an edge in the directed graph.
Definition: DirectedGraph.h:27
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::cl::desc
Definition: CommandLine.h:414
SimplifyDDG
static cl::opt< bool > SimplifyDDG("ddg-simplify", cl::init(true), cl::Hidden, cl::ZeroOrMore, cl::desc("Simplify DDG by merging nodes that have less interesting edges."))
llvm::DDGNode::NodeKind::Unknown
@ Unknown
llvm::DDGBuilder::mergeNodes
void mergeNodes(DDGNode &Src, DDGNode &Tgt) final override
Definition: DDG.cpp:280
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::DDGEdge::EdgeKind
EdgeKind
The kind of edge in the DDG.
Definition: DDG.h:222
llvm::DataDependenceGraph::DDGBuilder
friend class DDGBuilder
Definition: DDG.h:318
llvm::AbstractDependenceGraphBuilder< DataDependenceGraph >::Graph
DataDependenceGraph & Graph
Reference to the graph that gets built by a concrete implementation of this builder.
Definition: DependenceGraphBuilder.h:180