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(true), cl::Hidden, cl::ZeroOrMore,
21 cl::desc(
22 "Simplify DDG by merging nodes that have less interesting edges."));
23
24static 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
30template class llvm::DGEdge<DDGNode, DDGEdge>;
31template class llvm::DGNode<DDGNode, DDGEdge>;
32template class llvm::DirectedGraph<DDGNode, DDGEdge>;
33
34//===--------------------------------------------------------------------===//
35// DDGNode implementation
36//===--------------------------------------------------------------------===//
37DDGNode::~DDGNode() {}
38
39bool DDGNode::collectInstructions(
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.");
50 SmallVector<Instruction *, 8> TmpIList;
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
59raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
60 const char *Out;
61 switch (K) {
62 case DDGNode::NodeKind::SingleInstruction:
63 Out = "single-instruction";
64 break;
65 case DDGNode::NodeKind::MultiInstruction:
66 Out = "multi-instruction";
67 break;
68 case DDGNode::NodeKind::PiBlock:
69 Out = "pi-block";
70 break;
71 case DDGNode::NodeKind::Root:
72 Out = "root";
73 break;
74 case DDGNode::NodeKind::Unknown:
75 Out = "?? (error)";
76 break;
77 }
78 OS << Out;
79 return OS;
80}
81
82raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
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
108SimpleDDGNode::SimpleDDGNode(Instruction &I)
109 : DDGNode(NodeKind::SingleInstruction), InstList() {
110 assert(InstList.empty() && "Expected empty list.");
111 InstList.push_back(&I);
112}
113
114SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)
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
121SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
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
128SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
129
130//===--------------------------------------------------------------------===//
131// PiBlockDDGNode implementation
132//===--------------------------------------------------------------------===//
133
134PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List)
135 : DDGNode(NodeKind::PiBlock), NodeList(List) {
136 assert(!NodeList.empty() && "pi-block node constructed with an empty list.");
137}
138
139PiBlockDDGNode::PiBlockDDGNode(const PiBlockDDGNode &N)
140 : DDGNode(N), NodeList(N.NodeList) {
141 assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&
142 "constructing from invalid pi-block node.");
143}
144
145PiBlockDDGNode::PiBlockDDGNode(PiBlockDDGNode &&N)
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
151PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); }
152
153//===--------------------------------------------------------------------===//
154// DDGEdge implementation
155//===--------------------------------------------------------------------===//
156
157raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
158 const char *Out;
159 switch (K) {
160 case DDGEdge::EdgeKind::RegisterDefUse:
161 Out = "def-use";
162 break;
163 case DDGEdge::EdgeKind::MemoryDependence:
164 Out = "memory";
165 break;
166 case DDGEdge::EdgeKind::Rooted:
167 Out = "rooted";
168 break;
169 case DDGEdge::EdgeKind::Unknown:
170 Out = "?? (error)";
171 break;
172 }
173 OS << Out;
174 return OS;
175}
176
177raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
178 OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
179 return OS;
180}
181
182//===--------------------------------------------------------------------===//
183// DataDependenceGraph implementation
184//===--------------------------------------------------------------------===//
185using BasicBlockListType = SmallVector<BasicBlock *, 8>;
186
187DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
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
198DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI,
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
213DataDependenceGraph::~DataDependenceGraph() {
214 for (auto *N : Nodes) {
215 for (auto *E : *N)
216 delete E;
217 delete N;
218 }
219}
220
221bool DataDependenceGraph::addNode(DDGNode &N) {
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
244const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const {
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
253raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
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
267bool DDGBuilder::areNodesMergeable(const DDGNode &Src,
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
280void DDGBuilder::mergeNodes(DDGNode &A, DDGNode &B) {
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
300bool DDGBuilder::shouldSimplify() const { return SimplifyDDG; }
301
302bool DDGBuilder::shouldCreatePiBlocks() const { return CreatePiBlocks; }
303
304//===--------------------------------------------------------------------===//
305// DDG Analysis Passes
306//===--------------------------------------------------------------------===//
307
308/// DDG as a loop pass.
309DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
310 LoopStandardAnalysisResults &AR) {
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}
315AnalysisKey DDGAnalysis::Key;
316
317PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
318 LoopStandardAnalysisResults &AR,
319 LPMUpdater &U) {
320 OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
321 OS << *AM.getResult<DDGAnalysis>(L, AR);
322 return PreservedAnalyses::all();
323}
324