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 #define DEBUG_TYPE "ddg"
17 
18 template class llvm::DGEdge<DDGNode, DDGEdge>;
19 template class llvm::DGNode<DDGNode, DDGEdge>;
20 template class llvm::DirectedGraph<DDGNode, DDGEdge>;
21 
22 //===--------------------------------------------------------------------===//
23 // DDGNode implementation
24 //===--------------------------------------------------------------------===//
25 DDGNode::~DDGNode() {}
26 
27 bool DDGNode::collectInstructions(
28     llvm::function_ref<bool(Instruction *)> const &Pred,
29     InstructionListType &IList) const {
30   assert(IList.empty() && "Expected the IList to be empty on entry.");
31   if (isa<SimpleDDGNode>(this)) {
32     for (auto *I : cast<const SimpleDDGNode>(this)->getInstructions())
33       if (Pred(I))
34         IList.push_back(I);
35   } else
36     llvm_unreachable("unimplemented type of node");
37   return !IList.empty();
38 }
39 
40 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {
41   const char *Out;
42   switch (K) {
43   case DDGNode::NodeKind::SingleInstruction:
44     Out = "single-instruction";
45     break;
46   case DDGNode::NodeKind::MultiInstruction:
47     Out = "multi-instruction";
48     break;
49   case DDGNode::NodeKind::Unknown:
50     Out = "??";
51     break;
52   }
53   OS << Out;
54   return OS;
55 }
56 
57 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {
58   OS << "Node Address:" << &N << ":" << N.getKind() << "\n";
59   if (isa<SimpleDDGNode>(N)) {
60     OS << " Instructions:\n";
61     for (auto *I : cast<const SimpleDDGNode>(N).getInstructions())
62       OS.indent(2) << *I << "\n";
63   } else
64     llvm_unreachable("unimplemented type of node");
65 
66   OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");
67   for (auto &E : N.getEdges())
68     OS.indent(2) << *E;
69   return OS;
70 }
71 
72 //===--------------------------------------------------------------------===//
73 // SimpleDDGNode implementation
74 //===--------------------------------------------------------------------===//
75 
76 SimpleDDGNode::SimpleDDGNode(Instruction &I)
77   : DDGNode(NodeKind::SingleInstruction), InstList() {
78   assert(InstList.empty() && "Expected empty list.");
79   InstList.push_back(&I);
80 }
81 
82 SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)
83     : DDGNode(N), InstList(N.InstList) {
84   assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
85           (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
86          "constructing from invalid simple node.");
87 }
88 
89 SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)
90     : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {
91   assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||
92           (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&
93          "constructing from invalid simple node.");
94 }
95 
96 SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }
97 
98 //===--------------------------------------------------------------------===//
99 // DDGEdge implementation
100 //===--------------------------------------------------------------------===//
101 
102 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {
103   const char *Out;
104   switch (K) {
105   case DDGEdge::EdgeKind::RegisterDefUse:
106     Out = "def-use";
107     break;
108   case DDGEdge::EdgeKind::MemoryDependence:
109     Out = "memory";
110     break;
111   case DDGEdge::EdgeKind::Unknown:
112     Out = "??";
113     break;
114   }
115   OS << Out;
116   return OS;
117 }
118 
119 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {
120   OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";
121   return OS;
122 }
123 
124 //===--------------------------------------------------------------------===//
125 // DataDependenceGraph implementation
126 //===--------------------------------------------------------------------===//
127 using BasicBlockListType = SmallVector<BasicBlock *, 8>;
128 
129 DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)
130     : DependenceGraphInfo(F.getName().str(), D) {
131   BasicBlockListType BBList;
132   for (auto &BB : F.getBasicBlockList())
133     BBList.push_back(&BB);
134   DDGBuilder(*this, D, BBList).populate();
135 }
136 
137 DataDependenceGraph::DataDependenceGraph(const Loop &L, DependenceInfo &D)
138     : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +
139                                 L.getHeader()->getName())
140                               .str(),
141                           D) {
142   BasicBlockListType BBList;
143   for (BasicBlock *BB : L.blocks())
144     BBList.push_back(BB);
145   DDGBuilder(*this, D, BBList).populate();
146 }
147 
148 DataDependenceGraph::~DataDependenceGraph() {
149   for (auto *N : Nodes) {
150     for (auto *E : *N)
151       delete E;
152     delete N;
153   }
154 }
155 
156 raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {
157   for (auto *Node : G)
158     OS << *Node << "\n";
159   return OS;
160 }
161 
162 //===--------------------------------------------------------------------===//
163 // DDG Analysis Passes
164 //===--------------------------------------------------------------------===//
165 
166 /// DDG as a loop pass.
167 DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,
168                                      LoopStandardAnalysisResults &AR) {
169   Function *F = L.getHeader()->getParent();
170   DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);
171   return std::make_unique<DataDependenceGraph>(L, DI);
172 }
173 AnalysisKey DDGAnalysis::Key;
174 
175 PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,
176                                               LoopStandardAnalysisResults &AR,
177                                               LPMUpdater &U) {
178   OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";
179   OS << *AM.getResult<DDGAnalysis>(L, AR);
180   return PreservedAnalyses::all();
181 }
182