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"
14#include "llvm/Analysis/LoopIterator.h"
15#include "llvm/Support/CommandLine.h"
16
17using namespace llvm;
18
19static cl::opt<bool> SimplifyDDG(
20 "ddg-simplify", cl::init(Val: true), cl::Hidden,
21 cl::desc(
22 "Simplify DDG by merging nodes that have less interesting edges."));
23
24static cl::opt<bool> CreatePiBlocks("ddg-pi-blocks", cl::init(Val: true), cl::Hidden,
25 cl::desc("Create pi-block nodes."));
26
27#define DEBUG_TYPE "ddg"
28
29template class llvm::DGEdge<DDGNode, DDGEdge>;
30template class llvm::DGNode<DDGNode, DDGEdge>;
31template class llvm::DirectedGraph<DDGNode, DDGEdge>;
32
33//===--------------------------------------------------------------------===//
34// DDGNode implementation
35//===--------------------------------------------------------------------===//
36DDGNode::~DDGNode() = default;
37
38bool DDGNode::collectInstructions(
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>(Val: this)) {
43 for (Instruction *I : cast<const SimpleDDGNode>(Val: this)->getInstructions())
44 if (Pred(I))
45 IList.push_back(Elt: I);
46 } else if (isa<PiBlockDDGNode>(Val: this)) {
47 for (const DDGNode *PN : cast<const PiBlockDDGNode>(Val: this)->getNodes()) {
48 assert(!isa<PiBlockDDGNode>(PN) && "Nested PiBlocks are not supported.");
49 SmallVector<Instruction *, 8> TmpIList;
50 PN->collectInstructions(Pred, IList&: TmpIList);
51 llvm::append_range(C&: IList, R&: TmpIList);
52 }
53 } else
54 llvm_unreachable("unimplemented type of node");
55 return !IList.empty();
56}
57
58raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
59 const char *Out;
60 switch (K) {
61 case DDGNode::NodeKind::SingleInstruction:
62 Out = "single-instruction";
63 break;
64 case DDGNode::NodeKind::MultiInstruction:
65 Out = "multi-instruction";
66 break;
67 case DDGNode::NodeKind::PiBlock:
68 Out = "pi-block";
69 break;
70 case DDGNode::NodeKind::Root:
71 Out = "root";
72 break;
73 case DDGNode::NodeKind::Unknown:
74 Out = "?? (error)";
75 break;
76 }
77 OS << Out;
78 return OS;
79}
80
81raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
82 OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
83 if (isa<SimpleDDGNode>(Val: N)) {
84 OS << " Instructions:\n";
85 for (const Instruction *I : cast<const SimpleDDGNode>(Val: N).getInstructions())
86 OS.indent(NumSpaces: 2) << *I << "\n";
87 } else if (isa<PiBlockDDGNode>(Val: &N)) {
88 OS << "--- start of nodes in pi-block ---\n";
89 auto &Nodes = cast<const PiBlockDDGNode>(Val: &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>(Val: 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(NumSpaces: 2) << *E;
100 return OS;
101}
102
103//===--------------------------------------------------------------------===//
104// SimpleDDGNode implementation
105//===--------------------------------------------------------------------===//
106
107SimpleDDGNode::SimpleDDGNode(Instruction &I)
108 : DDGNode(NodeKind::SingleInstruction) {
109 assert(InstList.empty() && "Expected empty list.");
110 InstList.push_back(Elt: &I);
111}
112
113SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)
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
120SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
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
133PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List)
134 : DDGNode(NodeKind::PiBlock), NodeList(List) {
135 assert(!NodeList.empty() && "pi-block node constructed with an empty list.");
136}
137
138PiBlockDDGNode::PiBlockDDGNode(const PiBlockDDGNode &N)
139 : DDGNode(N), NodeList(N.NodeList) {
140 assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
141 "constructing from invalid pi-block node.");
142}
143
144PiBlockDDGNode::PiBlockDDGNode(PiBlockDDGNode &&N)
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
150PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); }
151
152//===--------------------------------------------------------------------===//
153// DDGEdge implementation
154//===--------------------------------------------------------------------===//
155
156raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
157 const char *Out;
158 switch (K) {
159 case DDGEdge::EdgeKind::RegisterDefUse:
160 Out = "def-use";
161 break;
162 case DDGEdge::EdgeKind::MemoryDependence:
163 Out = "memory";
164 break;
165 case DDGEdge::EdgeKind::Rooted:
166 Out = "rooted";
167 break;
168 case DDGEdge::EdgeKind::Unknown:
169 Out = "?? (error)";
170 break;
171 }
172 OS << Out;
173 return OS;
174}
175
176raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
177 OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
178 return OS;
179}
180
181//===--------------------------------------------------------------------===//
182// DataDependenceGraph implementation
183//===--------------------------------------------------------------------===//
184using BasicBlockListType = SmallVector<BasicBlock *, 8>;
185
186DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
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(x: scc_begin(G: &F), y: scc_end(G: &F)))
192 append_range(C&: BBList, R: SCC);
193 std::reverse(first: BBList.begin(), last: BBList.end());
194 DDGBuilder(*this, D, BBList).populate();
195}
196
197DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI,
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: &LI);
207 BasicBlockListType BBList;
208 append_range(C&: BBList, R: make_range(x: DFS.beginRPO(), y: DFS.endRPO()));
209 DDGBuilder(*this, D, BBList).populate();
210}
211
212DataDependenceGraph::~DataDependenceGraph() {
213 for (auto *N : Nodes) {
214 for (auto *E : *N)
215 delete E;
216 delete N;
217 }
218}
219
220bool DataDependenceGraph::addNode(DDGNode &N) {
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>(Val: &N);
230 assert((!Root || Pi) &&
231 "Root node is already added. No more nodes can be added.");
232
233 if (isa<RootDDGNode>(Val: N))
234 Root = &N;
235
236 if (Pi)
237 for (DDGNode *NI : Pi->getNodes())
238 PiBlockMap.insert(KV: std::make_pair(x&: NI, y&: Pi));
239
240 return true;
241}
242
243const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const {
244 auto It = PiBlockMap.find(Val: &N);
245 if (It == PiBlockMap.end())
246 return nullptr;
247 auto *Pi = It->second;
248 assert(!PiBlockMap.contains(Pi) && "Nested pi-blocks detected.");
249 return Pi;
250}
251
252raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
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(N: *Node))
257 OS << *Node << "\n";
258 OS << "\n";
259 return OS;
260}
261
262//===--------------------------------------------------------------------===//
263// DDGBuilder implementation
264//===--------------------------------------------------------------------===//
265
266bool DDGBuilder::areNodesMergeable(const DDGNode &Src,
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>(Val: &Src);
271 const auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(Val: &Tgt);
272 if (!SimpleSrc || !SimpleTgt)
273 return false;
274
275 return SimpleSrc->getLastInstruction()->getParent() ==
276 SimpleTgt->getFirstInstruction()->getParent();
277}
278
279void DDGBuilder::mergeNodes(DDGNode &A, DDGNode &B) {
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>(Val: &A)->appendInstructions(Input: *cast<SimpleDDGNode>(Val: &B));
288
289 // Move to A any outgoing edges from B.
290 for (DDGEdge *BE : B)
291 Graph.connect(Src&: A, Dst&: BE->getTargetNode(), E&: *BE);
292
293 A.removeEdge(E&: EdgeToFold);
294 destroyEdge(E&: EdgeToFold);
295 Graph.removeNode(N&: B);
296 destroyNode(N&: B);
297}
298
299bool DDGBuilder::shouldSimplify() const { return SimplifyDDG; }
300
301bool DDGBuilder::shouldCreatePiBlocks() const { return CreatePiBlocks; }
302
303//===--------------------------------------------------------------------===//
304// DDG Analysis Passes
305//===--------------------------------------------------------------------===//
306
307/// DDG as a loop pass.
308DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
309 LoopStandardAnalysisResults &AR) {
310 Function *F = L.getHeader()->getParent();
311 DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
312 return std::make_unique<DataDependenceGraph>(args&: L, args&: AR.LI, args&: DI);
313}
314AnalysisKey DDGAnalysis::Key;
315
316PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
317 LoopStandardAnalysisResults &AR,
318 LPMUpdater &U) {
319 OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
320 OS << *AM.getResult<DDGAnalysis>(IR&: L, ExtraArgs&: AR);
321 return PreservedAnalyses::all();
322}
323