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) { 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