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