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 "AnalysisOptions.h"
13#include "llvm/ADT/SCCIterator.h"
14#include "llvm/Analysis/LoopInfo.h"
15#include "llvm/Analysis/LoopIterator.h"
16
17using namespace llvm;
18
19#define DEBUG_TYPE "ddg"
20
21template class llvm::DGEdge<DDGNode, DDGEdge>;
22template class llvm::DGNode<DDGNode, DDGEdge>;
23template class llvm::DirectedGraph<DDGNode, DDGEdge>;
24
25//===--------------------------------------------------------------------===//
26// DDGNode implementation
27//===--------------------------------------------------------------------===//
28DDGNode::~DDGNode() = default;
29
30bool DDGNode::collectInstructions(
31 llvm::function_ref<bool(Instruction *)> const &Pred,
32 InstructionListType &IList) const {
33 assert(IList.empty() && "Expected the IList to be empty on entry.");
34 if (isa<SimpleDDGNode>(Val: this)) {
35 for (Instruction *I : cast<const SimpleDDGNode>(Val: this)->getInstructions())
36 if (Pred(I))
37 IList.push_back(Elt: I);
38 } else if (isa<PiBlockDDGNode>(Val: this)) {
39 for (const DDGNode *PN : cast<const PiBlockDDGNode>(Val: this)->getNodes()) {
40 assert(!isa<PiBlockDDGNode>(PN) && "Nested PiBlocks are not supported.");
41 SmallVector<Instruction *, 8> TmpIList;
42 PN->collectInstructions(Pred, IList&: TmpIList);
43 llvm::append_range(C&: IList, R&: TmpIList);
44 }
45 } else
46 llvm_unreachable("unimplemented type of node");
47 return !IList.empty();
48}
49
50raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
51 const char *Out;
52 switch (K) {
53 case DDGNode::NodeKind::SingleInstruction:
54 Out = "single-instruction";
55 break;
56 case DDGNode::NodeKind::MultiInstruction:
57 Out = "multi-instruction";
58 break;
59 case DDGNode::NodeKind::PiBlock:
60 Out = "pi-block";
61 break;
62 case DDGNode::NodeKind::Root:
63 Out = "root";
64 break;
65 case DDGNode::NodeKind::Unknown:
66 Out = "?? (error)";
67 break;
68 }
69 OS << Out;
70 return OS;
71}
72
73raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
74 OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
75 if (isa<SimpleDDGNode>(Val: N)) {
76 OS << " Instructions:\n";
77 for (const Instruction *I : cast<const SimpleDDGNode>(Val: N).getInstructions())
78 OS.indent(NumSpaces: 2) << *I << "\n";
79 } else if (isa<PiBlockDDGNode>(Val: &N)) {
80 OS << "--- start of nodes in pi-block ---\n";
81 auto &Nodes = cast<const PiBlockDDGNode>(Val: &N)->getNodes();
82 unsigned Count = 0;
83 for (const DDGNode *N : Nodes)
84 OS << *N << (++Count == Nodes.size() ? "" : "\n");
85 OS << "--- end of nodes in pi-block ---\n";
86 } else if (!isa<RootDDGNode>(Val: N))
87 llvm_unreachable("unimplemented type of node");
88
89 OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
90 for (const auto &E : N.getEdges())
91 OS.indent(NumSpaces: 2) << *E;
92 return OS;
93}
94
95//===--------------------------------------------------------------------===//
96// SimpleDDGNode implementation
97//===--------------------------------------------------------------------===//
98
99SimpleDDGNode::SimpleDDGNode(Instruction &I)
100 : DDGNode(NodeKind::SingleInstruction) {
101 assert(InstList.empty() && "Expected empty list.");
102 InstList.push_back(Elt: &I);
103}
104
105SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)
106 : DDGNode(N), InstList(N.InstList) {
107 assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
108 (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
109 "constructing from invalid simple node.");
110}
111
112SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
113 : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {
114 assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
115 (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
116 "constructing from invalid simple node.");
117}
118
119SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
120
121//===--------------------------------------------------------------------===//
122// PiBlockDDGNode implementation
123//===--------------------------------------------------------------------===//
124
125PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List)
126 : DDGNode(NodeKind::PiBlock), NodeList(List) {
127 assert(!NodeList.empty() && "pi-block node constructed with an empty list.");
128}
129
130PiBlockDDGNode::PiBlockDDGNode(const PiBlockDDGNode &N)
131 : DDGNode(N), NodeList(N.NodeList) {
132 assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
133 "constructing from invalid pi-block node.");
134}
135
136PiBlockDDGNode::PiBlockDDGNode(PiBlockDDGNode &&N)
137 : DDGNode(std::move(N)), NodeList(std::move(N.NodeList)) {
138 assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
139 "constructing from invalid pi-block node.");
140}
141
142PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); }
143
144//===--------------------------------------------------------------------===//
145// DDGEdge implementation
146//===--------------------------------------------------------------------===//
147
148raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
149 const char *Out;
150 switch (K) {
151 case DDGEdge::EdgeKind::RegisterDefUse:
152 Out = "def-use";
153 break;
154 case DDGEdge::EdgeKind::MemoryDependence:
155 Out = "memory";
156 break;
157 case DDGEdge::EdgeKind::Rooted:
158 Out = "rooted";
159 break;
160 case DDGEdge::EdgeKind::Unknown:
161 Out = "?? (error)";
162 break;
163 }
164 OS << Out;
165 return OS;
166}
167
168raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
169 OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
170 return OS;
171}
172
173//===--------------------------------------------------------------------===//
174// DataDependenceGraph implementation
175//===--------------------------------------------------------------------===//
176using BasicBlockListType = SmallVector<BasicBlock *, 8>;
177
178DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
179 : DependenceGraphInfo(F.getName().str(), D) {
180 // Put the basic blocks in program order for correct dependence
181 // directions.
182 BasicBlockListType BBList;
183 for (const auto &SCC : make_range(x: scc_begin(G: &F), y: scc_end(G: &F)))
184 append_range(C&: BBList, R: SCC);
185 std::reverse(first: BBList.begin(), last: BBList.end());
186 DDGBuilder(*this, D, BBList).populate();
187}
188
189DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI,
190 DependenceInfo &D)
191 : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
192 L.getHeader()->getName())
193 .str(),
194 D) {
195 // Put the basic blocks in program order for correct dependence
196 // directions.
197 LoopBlocksDFS DFS(&L);
198 DFS.perform(LI: &LI);
199 BasicBlockListType BBList;
200 append_range(C&: BBList, R: make_range(x: DFS.beginRPO(), y: DFS.endRPO()));
201 DDGBuilder(*this, D, BBList).populate();
202}
203
204DataDependenceGraph::~DataDependenceGraph() {
205 for (auto *N : Nodes) {
206 for (auto *E : *N)
207 delete E;
208 delete N;
209 }
210}
211
212bool DataDependenceGraph::addNode(DDGNode &N) {
213 if (!DDGBase::addNode(N))
214 return false;
215
216 // In general, if the root node is already created and linked, it is not safe
217 // to add new nodes since they may be unreachable by the root. However,
218 // pi-block nodes need to be added after the root node is linked, and they are
219 // always reachable by the root, because they represent components that are
220 // already reachable by root.
221 auto *Pi = dyn_cast<PiBlockDDGNode>(Val: &N);
222 assert((!Root || Pi) &&
223 "Root node is already added. No more nodes can be added.");
224
225 if (isa<RootDDGNode>(Val: N))
226 Root = &N;
227
228 if (Pi)
229 for (DDGNode *NI : Pi->getNodes())
230 PiBlockMap.insert(KV: std::make_pair(x&: NI, y&: Pi));
231
232 return true;
233}
234
235const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const {
236 auto It = PiBlockMap.find(Val: &N);
237 if (It == PiBlockMap.end())
238 return nullptr;
239 auto *Pi = It->second;
240 assert(!PiBlockMap.contains(Pi) && "Nested pi-blocks detected.");
241 return Pi;
242}
243
244raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
245 for (DDGNode *Node : G)
246 // Avoid printing nodes that are part of a pi-block twice. They will get
247 // printed when the pi-block is printed.
248 if (!G.getPiBlock(N: *Node))
249 OS << *Node << "\n";
250 OS << "\n";
251 return OS;
252}
253
254//===--------------------------------------------------------------------===//
255// DDGBuilder implementation
256//===--------------------------------------------------------------------===//
257
258bool DDGBuilder::areNodesMergeable(const DDGNode &Src,
259 const DDGNode &Tgt) const {
260 // Only merge two nodes if they are both simple nodes and the consecutive
261 // instructions after merging belong to the same BB.
262 const auto *SimpleSrc = dyn_cast<const SimpleDDGNode>(Val: &Src);
263 const auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(Val: &Tgt);
264 if (!SimpleSrc || !SimpleTgt)
265 return false;
266
267 return SimpleSrc->getLastInstruction()->getParent() ==
268 SimpleTgt->getFirstInstruction()->getParent();
269}
270
271void DDGBuilder::mergeNodes(DDGNode &A, DDGNode &B) {
272 DDGEdge &EdgeToFold = A.back();
273 assert(A.getEdges().size() == 1 && EdgeToFold.getTargetNode() == B &&
274 "Expected A to have a single edge to B.");
275 assert(isa<SimpleDDGNode>(&A) && isa<SimpleDDGNode>(&B) &&
276 "Expected simple nodes");
277
278 // Copy instructions from B to the end of A.
279 cast<SimpleDDGNode>(Val: &A)->appendInstructions(Input: *cast<SimpleDDGNode>(Val: &B));
280
281 // Move to A any outgoing edges from B.
282 for (DDGEdge *BE : B)
283 Graph.connect(Src&: A, Dst&: BE->getTargetNode(), E&: *BE);
284
285 A.removeEdge(E&: EdgeToFold);
286 destroyEdge(E&: EdgeToFold);
287 Graph.removeNode(N&: B);
288 destroyNode(N&: B);
289}
290
291bool DDGBuilder::shouldSimplify() const {
292 return getAnalysisOptions(F: *DI.getFunction()).ddg_simplify;
293}
294
295bool DDGBuilder::shouldCreatePiBlocks() const {
296 return getAnalysisOptions(F: *DI.getFunction()).ddg_pi_blocks;
297}
298
299//===--------------------------------------------------------------------===//
300// DDG Analysis Passes
301//===--------------------------------------------------------------------===//
302
303/// DDG as a loop pass.
304DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
305 LoopStandardAnalysisResults &AR) {
306 Function *F = L.getHeader()->getParent();
307 DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
308 return std::make_unique<DataDependenceGraph>(args&: L, args&: AR.LI, args&: DI);
309}
310AnalysisKey DDGAnalysis::Key;
311
312PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
313 LoopStandardAnalysisResults &AR,
314 LPMUpdater &U) {
315 OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
316 OS << *AM.getResult<DDGAnalysis>(IR&: L, ExtraArgs&: AR);
317 return PreservedAnalyses::all();
318}
319