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> 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 
24 static 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 
30 template class llvm::DGEdge<DDGNode, DDGEdge>;
31 template class llvm::DGNode<DDGNode, DDGEdge>;
32 template class llvm::DirectedGraph<DDGNode, DDGEdge>;
33 
34 //===--------------------------------------------------------------------===//
35 // DDGNode implementation
36 //===--------------------------------------------------------------------===//
37 DDGNode::~DDGNode() {}
38 
39 bool 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 
59 raw_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 
82 raw_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 
108 SimpleDDGNode::SimpleDDGNode(Instruction &I)
109   : DDGNode(NodeKind::SingleInstruction), InstList() {
110   assert(InstList.empty() && "Expected empty list.");
111   InstList.push_back(&I);
112 }
113 
114 SimpleDDGNode::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 
121 SimpleDDGNode::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 
128 SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
129 
130 //===--------------------------------------------------------------------===//
131 // PiBlockDDGNode implementation
132 //===--------------------------------------------------------------------===//
133 
134 PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List)
135     : DDGNode(NodeKind::PiBlock), NodeList(List) {
136   assert(!NodeList.empty() && "pi-block node constructed with an empty list.");
137 }
138 
139 PiBlockDDGNode::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 
145 PiBlockDDGNode::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 
151 PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); }
152 
153 //===--------------------------------------------------------------------===//
154 // DDGEdge implementation
155 //===--------------------------------------------------------------------===//
156 
157 raw_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 
177 raw_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 //===--------------------------------------------------------------------===//
185 using BasicBlockListType = SmallVector<BasicBlock *, 8>;
186 
187 DataDependenceGraph::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 
198 DataDependenceGraph::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 
213 DataDependenceGraph::~DataDependenceGraph() {
214   for (auto *N : Nodes) {
215     for (auto *E : *N)
216       delete E;
217     delete N;
218   }
219 }
220 
221 bool 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 
244 const 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 
253 raw_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 
267 bool 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 
280 void 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 
300 bool DDGBuilder::shouldSimplify() const { return SimplifyDDG; }
301 
302 bool DDGBuilder::shouldCreatePiBlocks() const { return CreatePiBlocks; }
303 
304 //===--------------------------------------------------------------------===//
305 // DDG Analysis Passes
306 //===--------------------------------------------------------------------===//
307 
308 /// DDG as a loop pass.
309 DDGAnalysis::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 }
315 AnalysisKey DDGAnalysis::Key;
316 
317 PreservedAnalyses 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