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