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 //===--------------------------------------------------------------------===//
32 DDGNode::~DDGNode() {}
33 
34 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 
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 
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 
103 SimpleDDGNode::SimpleDDGNode(Instruction &I)
104   : DDGNode(NodeKind::SingleInstruction), InstList() {
105   assert(InstList.empty() && "Expected empty list.");
106   InstList.push_back(&I);
107 }
108 
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 
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 
123 SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
124 
125 //===--------------------------------------------------------------------===//
126 // PiBlockDDGNode implementation
127 //===--------------------------------------------------------------------===//
128 
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 
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 
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 
146 PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); }
147 
148 //===--------------------------------------------------------------------===//
149 // DDGEdge implementation
150 //===--------------------------------------------------------------------===//
151 
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 
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 
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 
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 
210 DataDependenceGraph::~DataDependenceGraph() {
211   for (auto *N : Nodes) {
212     for (auto *E : *N)
213       delete E;
214     delete N;
215   }
216 }
217 
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 
241 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 
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 
260 bool DDGBuilder::shouldCreatePiBlocks() const {
261   return CreatePiBlocks;
262 }
263 
264 //===--------------------------------------------------------------------===//
265 // DDG Analysis Passes
266 //===--------------------------------------------------------------------===//
267 
268 /// DDG as a loop pass.
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 
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