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::Root: 50 Out = "root"; 51 break; 52 case DDGNode::NodeKind::Unknown: 53 Out = "??"; 54 break; 55 } 56 OS << Out; 57 return OS; 58 } 59 60 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) { 61 OS << "Node Address:" << &N << ":" << N.getKind() << "\n"; 62 if (isa<SimpleDDGNode>(N)) { 63 OS << " Instructions:\n"; 64 for (auto *I : cast<const SimpleDDGNode>(N).getInstructions()) 65 OS.indent(2) << *I << "\n"; 66 } else if (!isa<RootDDGNode>(N)) 67 llvm_unreachable("unimplemented type of node"); 68 69 OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n"); 70 for (auto &E : N.getEdges()) 71 OS.indent(2) << *E; 72 return OS; 73 } 74 75 //===--------------------------------------------------------------------===// 76 // SimpleDDGNode implementation 77 //===--------------------------------------------------------------------===// 78 79 SimpleDDGNode::SimpleDDGNode(Instruction &I) 80 : DDGNode(NodeKind::SingleInstruction), InstList() { 81 assert(InstList.empty() && "Expected empty list."); 82 InstList.push_back(&I); 83 } 84 85 SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N) 86 : DDGNode(N), InstList(N.InstList) { 87 assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) || 88 (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) && 89 "constructing from invalid simple node."); 90 } 91 92 SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N) 93 : DDGNode(std::move(N)), InstList(std::move(N.InstList)) { 94 assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) || 95 (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) && 96 "constructing from invalid simple node."); 97 } 98 99 SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); } 100 101 //===--------------------------------------------------------------------===// 102 // DDGEdge implementation 103 //===--------------------------------------------------------------------===// 104 105 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) { 106 const char *Out; 107 switch (K) { 108 case DDGEdge::EdgeKind::RegisterDefUse: 109 Out = "def-use"; 110 break; 111 case DDGEdge::EdgeKind::MemoryDependence: 112 Out = "memory"; 113 break; 114 case DDGEdge::EdgeKind::Rooted: 115 Out = "rooted"; 116 break; 117 case DDGEdge::EdgeKind::Unknown: 118 Out = "??"; 119 break; 120 } 121 OS << Out; 122 return OS; 123 } 124 125 raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) { 126 OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n"; 127 return OS; 128 } 129 130 //===--------------------------------------------------------------------===// 131 // DataDependenceGraph implementation 132 //===--------------------------------------------------------------------===// 133 using BasicBlockListType = SmallVector<BasicBlock *, 8>; 134 135 DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D) 136 : DependenceGraphInfo(F.getName().str(), D) { 137 BasicBlockListType BBList; 138 for (auto &BB : F.getBasicBlockList()) 139 BBList.push_back(&BB); 140 DDGBuilder(*this, D, BBList).populate(); 141 } 142 143 DataDependenceGraph::DataDependenceGraph(const Loop &L, DependenceInfo &D) 144 : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." + 145 L.getHeader()->getName()) 146 .str(), 147 D) { 148 BasicBlockListType BBList; 149 for (BasicBlock *BB : L.blocks()) 150 BBList.push_back(BB); 151 DDGBuilder(*this, D, BBList).populate(); 152 } 153 154 DataDependenceGraph::~DataDependenceGraph() { 155 for (auto *N : Nodes) { 156 for (auto *E : *N) 157 delete E; 158 delete N; 159 } 160 } 161 162 bool DataDependenceGraph::addNode(DDGNode &N) { 163 if (!DDGBase::addNode(N)) 164 return false; 165 166 // In general, if the root node is already created and linked, it is not safe 167 // to add new nodes since they may be unreachable by the root. 168 // TODO: Allow adding Pi-block nodes after root is created. Pi-blocks are an 169 // exception because they represent components that are already reachable by 170 // root. 171 assert(!Root && "Root node is already added. No more nodes can be added."); 172 if (isa<RootDDGNode>(N)) 173 Root = &N; 174 175 return true; 176 } 177 178 raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) { 179 for (auto *Node : G) 180 OS << *Node << "\n"; 181 return OS; 182 } 183 184 //===--------------------------------------------------------------------===// 185 // DDG Analysis Passes 186 //===--------------------------------------------------------------------===// 187 188 /// DDG as a loop pass. 189 DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM, 190 LoopStandardAnalysisResults &AR) { 191 Function *F = L.getHeader()->getParent(); 192 DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI); 193 return std::make_unique<DataDependenceGraph>(L, DI); 194 } 195 AnalysisKey DDGAnalysis::Key; 196 197 PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM, 198 LoopStandardAnalysisResults &AR, 199 LPMUpdater &U) { 200 OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n"; 201 OS << *AM.getResult<DDGAnalysis>(L, AR); 202 return PreservedAnalyses::all(); 203 } 204