LLVM 17.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"
16
17using namespace llvm;
18
20 "ddg-simplify", cl::init(true), cl::Hidden,
22 "Simplify DDG by merging nodes that have less interesting edges."));
23
24static 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
32
33//===--------------------------------------------------------------------===//
34// DDGNode implementation
35//===--------------------------------------------------------------------===//
36DDGNode::~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 (const 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
127SimpleDDGNode::~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
140 assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
141 "constructing from invalid pi-block node.");
142}
143
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 (const 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
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);
296 destroyNode(B);
297}
298
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}
314AnalysisKey DDGAnalysis::Key;
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}
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static cl::opt< bool > CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::desc("Create pi-block nodes."))
static cl::opt< bool > SimplifyDDG("ddg-simplify", cl::init(true), cl::Hidden, cl::desc("Simplify DDG by merging nodes that have less interesting edges."))
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
static StringRef getName(Value *V)
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
virtual void destroyEdge(EdgeType &E)
Deallocate memory of edge E.
virtual void destroyNode(NodeType &N)
Deallocate memory of node N.
DataDependenceGraph & Graph
Reference to the graph that gets built by a concrete implementation of this builder.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:112
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: DDG.cpp:316
Analysis pass that builds the DDG for a loop.
Definition: DDG.h:414
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
DDG as a loop pass.
Definition: DDG.cpp:308
std::unique_ptr< DataDependenceGraph > Result
Definition: DDG.h:416
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
bool shouldCreatePiBlocks() const final
Return true if creation of pi-blocks are supported and desired, and false otherwise.
Definition: DDG.cpp:301
bool shouldSimplify() const final
Return true if graph simplification step is requested, and false otherwise.
Definition: DDG.cpp:299
void mergeNodes(DDGNode &Src, DDGNode &Tgt) final
Definition: DDG.cpp:279
Data Dependency Graph Edge.
Definition: DDG.h:213
EdgeKind
The kind of edge in the DDG.
Definition: DDG.h:216
Data Dependence Graph Node The graph can represent the following types of nodes:
Definition: DDG.h:44
NodeKind getKind() const
Getter for the kind of this node.
Definition: DDG.h:75
virtual ~DDGNode()=0
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
Represent an edge in the directed graph.
Definition: DirectedGraph.h:28
const NodeType & getTargetNode() const
Retrieve the target node this edge connects to.
Definition: DirectedGraph.h:48
Represent a node in the directed graph.
Definition: DirectedGraph.h:73
Data Dependency Graph.
Definition: DDG.h:306
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
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
friend class DDGBuilder
Definition: DDG.h:308
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
iterator end()
Definition: DenseMap.h:84
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Definition: DDG.h:255
NodeType * Root
Definition: DDG.h:300
DependenceInfo - This class is the main dependence-analysis driver.
Directed graph.
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 ...
bool addNode(NodeType &N)
Add the given node N to the graph if it is not already present.
bool removeNode(NodeType &N)
Remove the given node N from the graph.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
BlockT * getHeader() const
Definition: LoopInfo.h:105
Store the result of a depth first search within basic blocks contained by a single loop.
Definition: LoopIterator.h:97
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
Definition: LoopIterator.h:136
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
Definition: LoopInfo.cpp:1222
RPOIterator endRPO() const
Definition: LoopIterator.h:140
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
Subclass of DDGNode representing a pi-block.
Definition: DDG.h:170
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Subclass of DDGNode representing single or multi-instruction nodes.
Definition: DDG.h:108
bool empty() const
Definition: SmallVector.h:94
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:308
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2014
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:232
scc_iterator< T > scc_end(const T &G)
Construct the end iterator for a deduced graph type T.
Definition: SCCIterator.h:237
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
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:1862
Definition: BitVector.h:851
#define N
Determine the kind of a node from its type.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...