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