323 lines · cpp
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-exception6//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 17using namespace llvm;18 19static cl::opt<bool> SimplifyDDG(20 "ddg-simplify", cl::init(true), cl::Hidden,21 cl::desc(22 "Simplify DDG by merging nodes that have less interesting edges."));23 24static cl::opt<bool> CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden,25 cl::desc("Create pi-block nodes."));26 27#define DEBUG_TYPE "ddg"28 29template class llvm::DGEdge<DDGNode, DDGEdge>;30template class llvm::DGNode<DDGNode, DDGEdge>;31template class llvm::DirectedGraph<DDGNode, DDGEdge>;32 33//===--------------------------------------------------------------------===//34// DDGNode implementation35//===--------------------------------------------------------------------===//36DDGNode::~DDGNode() = default;37 38bool DDGNode::collectInstructions(39 llvm::function_ref<bool(Instruction *)> const &Pred,40 InstructionListType &IList) const {41 assert(IList.empty() && "Expected the IList to be empty on entry.");42 if (isa<SimpleDDGNode>(this)) {43 for (Instruction *I : cast<const SimpleDDGNode>(this)->getInstructions())44 if (Pred(I))45 IList.push_back(I);46 } else if (isa<PiBlockDDGNode>(this)) {47 for (const DDGNode *PN : cast<const PiBlockDDGNode>(this)->getNodes()) {48 assert(!isa<PiBlockDDGNode>(PN) && "Nested PiBlocks are not supported.");49 SmallVector<Instruction *, 8> TmpIList;50 PN->collectInstructions(Pred, TmpIList);51 llvm::append_range(IList, TmpIList);52 }53 } else54 llvm_unreachable("unimplemented type of node");55 return !IList.empty();56}57 58raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode::NodeKind K) {59 const char *Out;60 switch (K) {61 case DDGNode::NodeKind::SingleInstruction:62 Out = "single-instruction";63 break;64 case DDGNode::NodeKind::MultiInstruction:65 Out = "multi-instruction";66 break;67 case DDGNode::NodeKind::PiBlock:68 Out = "pi-block";69 break;70 case DDGNode::NodeKind::Root:71 Out = "root";72 break;73 case DDGNode::NodeKind::Unknown:74 Out = "?? (error)";75 break;76 }77 OS << Out;78 return OS;79}80 81raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGNode &N) {82 OS << "Node Address:" << &N << ":" << N.getKind() << "\n";83 if (isa<SimpleDDGNode>(N)) {84 OS << " Instructions:\n";85 for (const Instruction *I : cast<const SimpleDDGNode>(N).getInstructions())86 OS.indent(2) << *I << "\n";87 } else if (isa<PiBlockDDGNode>(&N)) {88 OS << "--- start of nodes in pi-block ---\n";89 auto &Nodes = cast<const PiBlockDDGNode>(&N)->getNodes();90 unsigned Count = 0;91 for (const DDGNode *N : Nodes)92 OS << *N << (++Count == Nodes.size() ? "" : "\n");93 OS << "--- end of nodes in pi-block ---\n";94 } else if (!isa<RootDDGNode>(N))95 llvm_unreachable("unimplemented type of node");96 97 OS << (N.getEdges().empty() ? " Edges:none!\n" : " Edges:\n");98 for (const auto &E : N.getEdges())99 OS.indent(2) << *E;100 return OS;101}102 103//===--------------------------------------------------------------------===//104// SimpleDDGNode implementation105//===--------------------------------------------------------------------===//106 107SimpleDDGNode::SimpleDDGNode(Instruction &I)108 : DDGNode(NodeKind::SingleInstruction) {109 assert(InstList.empty() && "Expected empty list.");110 InstList.push_back(&I);111}112 113SimpleDDGNode::SimpleDDGNode(const SimpleDDGNode &N)114 : DDGNode(N), InstList(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 120SimpleDDGNode::SimpleDDGNode(SimpleDDGNode &&N)121 : DDGNode(std::move(N)), InstList(std::move(N.InstList)) {122 assert(((getKind() == NodeKind::SingleInstruction && InstList.size() == 1) ||123 (getKind() == NodeKind::MultiInstruction && InstList.size() > 1)) &&124 "constructing from invalid simple node.");125}126 127SimpleDDGNode::~SimpleDDGNode() { InstList.clear(); }128 129//===--------------------------------------------------------------------===//130// PiBlockDDGNode implementation131//===--------------------------------------------------------------------===//132 133PiBlockDDGNode::PiBlockDDGNode(const PiNodeList &List)134 : DDGNode(NodeKind::PiBlock), NodeList(List) {135 assert(!NodeList.empty() && "pi-block node constructed with an empty list.");136}137 138PiBlockDDGNode::PiBlockDDGNode(const PiBlockDDGNode &N)139 : DDGNode(N), NodeList(N.NodeList) {140 assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&141 "constructing from invalid pi-block node.");142}143 144PiBlockDDGNode::PiBlockDDGNode(PiBlockDDGNode &&N)145 : DDGNode(std::move(N)), NodeList(std::move(N.NodeList)) {146 assert(getKind() == NodeKind::PiBlock && !NodeList.empty() &&147 "constructing from invalid pi-block node.");148}149 150PiBlockDDGNode::~PiBlockDDGNode() { NodeList.clear(); }151 152//===--------------------------------------------------------------------===//153// DDGEdge implementation154//===--------------------------------------------------------------------===//155 156raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge::EdgeKind K) {157 const char *Out;158 switch (K) {159 case DDGEdge::EdgeKind::RegisterDefUse:160 Out = "def-use";161 break;162 case DDGEdge::EdgeKind::MemoryDependence:163 Out = "memory";164 break;165 case DDGEdge::EdgeKind::Rooted:166 Out = "rooted";167 break;168 case DDGEdge::EdgeKind::Unknown:169 Out = "?? (error)";170 break;171 }172 OS << Out;173 return OS;174}175 176raw_ostream &llvm::operator<<(raw_ostream &OS, const DDGEdge &E) {177 OS << "[" << E.getKind() << "] to " << &E.getTargetNode() << "\n";178 return OS;179}180 181//===--------------------------------------------------------------------===//182// DataDependenceGraph implementation183//===--------------------------------------------------------------------===//184using BasicBlockListType = SmallVector<BasicBlock *, 8>;185 186DataDependenceGraph::DataDependenceGraph(Function &F, DependenceInfo &D)187 : DependenceGraphInfo(F.getName().str(), D) {188 // Put the basic blocks in program order for correct dependence189 // directions.190 BasicBlockListType BBList;191 for (const auto &SCC : make_range(scc_begin(&F), scc_end(&F)))192 append_range(BBList, SCC);193 std::reverse(BBList.begin(), BBList.end());194 DDGBuilder(*this, D, BBList).populate();195}196 197DataDependenceGraph::DataDependenceGraph(Loop &L, LoopInfo &LI,198 DependenceInfo &D)199 : DependenceGraphInfo(Twine(L.getHeader()->getParent()->getName() + "." +200 L.getHeader()->getName())201 .str(),202 D) {203 // Put the basic blocks in program order for correct dependence204 // directions.205 LoopBlocksDFS DFS(&L);206 DFS.perform(&LI);207 BasicBlockListType BBList;208 append_range(BBList, make_range(DFS.beginRPO(), DFS.endRPO()));209 DDGBuilder(*this, D, BBList).populate();210}211 212DataDependenceGraph::~DataDependenceGraph() {213 for (auto *N : Nodes) {214 for (auto *E : *N)215 delete E;216 delete N;217 }218}219 220bool DataDependenceGraph::addNode(DDGNode &N) {221 if (!DDGBase::addNode(N))222 return false;223 224 // In general, if the root node is already created and linked, it is not safe225 // to add new nodes since they may be unreachable by the root. However,226 // pi-block nodes need to be added after the root node is linked, and they are227 // always reachable by the root, because they represent components that are228 // already reachable by root.229 auto *Pi = dyn_cast<PiBlockDDGNode>(&N);230 assert((!Root || Pi) &&231 "Root node is already added. No more nodes can be added.");232 233 if (isa<RootDDGNode>(N))234 Root = &N;235 236 if (Pi)237 for (DDGNode *NI : Pi->getNodes())238 PiBlockMap.insert(std::make_pair(NI, Pi));239 240 return true;241}242 243const PiBlockDDGNode *DataDependenceGraph::getPiBlock(const NodeType &N) const {244 auto It = PiBlockMap.find(&N);245 if (It == PiBlockMap.end())246 return nullptr;247 auto *Pi = It->second;248 assert(!PiBlockMap.contains(Pi) && "Nested pi-blocks detected.");249 return Pi;250}251 252raw_ostream &llvm::operator<<(raw_ostream &OS, const DataDependenceGraph &G) {253 for (DDGNode *Node : G)254 // Avoid printing nodes that are part of a pi-block twice. They will get255 // printed when the pi-block is printed.256 if (!G.getPiBlock(*Node))257 OS << *Node << "\n";258 OS << "\n";259 return OS;260}261 262//===--------------------------------------------------------------------===//263// DDGBuilder implementation264//===--------------------------------------------------------------------===//265 266bool DDGBuilder::areNodesMergeable(const DDGNode &Src,267 const DDGNode &Tgt) const {268 // Only merge two nodes if they are both simple nodes and the consecutive269 // instructions after merging belong to the same BB.270 const auto *SimpleSrc = dyn_cast<const SimpleDDGNode>(&Src);271 const auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(&Tgt);272 if (!SimpleSrc || !SimpleTgt)273 return false;274 275 return SimpleSrc->getLastInstruction()->getParent() ==276 SimpleTgt->getFirstInstruction()->getParent();277}278 279void DDGBuilder::mergeNodes(DDGNode &A, DDGNode &B) {280 DDGEdge &EdgeToFold = A.back();281 assert(A.getEdges().size() == 1 && EdgeToFold.getTargetNode() == B &&282 "Expected A to have a single edge to B.");283 assert(isa<SimpleDDGNode>(&A) && isa<SimpleDDGNode>(&B) &&284 "Expected simple nodes");285 286 // Copy instructions from B to the end of A.287 cast<SimpleDDGNode>(&A)->appendInstructions(*cast<SimpleDDGNode>(&B));288 289 // Move to A any outgoing edges from B.290 for (DDGEdge *BE : B)291 Graph.connect(A, BE->getTargetNode(), *BE);292 293 A.removeEdge(EdgeToFold);294 destroyEdge(EdgeToFold);295 Graph.removeNode(B);296 destroyNode(B);297}298 299bool DDGBuilder::shouldSimplify() const { return SimplifyDDG; }300 301bool DDGBuilder::shouldCreatePiBlocks() const { return CreatePiBlocks; }302 303//===--------------------------------------------------------------------===//304// DDG Analysis Passes305//===--------------------------------------------------------------------===//306 307/// DDG as a loop pass.308DDGAnalysis::Result DDGAnalysis::run(Loop &L, LoopAnalysisManager &AM,309 LoopStandardAnalysisResults &AR) {310 Function *F = L.getHeader()->getParent();311 DependenceInfo DI(F, &AR.AA, &AR.SE, &AR.LI);312 return std::make_unique<DataDependenceGraph>(L, AR.LI, DI);313}314AnalysisKey DDGAnalysis::Key;315 316PreservedAnalyses DDGAnalysisPrinterPass::run(Loop &L, LoopAnalysisManager &AM,317 LoopStandardAnalysisResults &AR,318 LPMUpdater &U) {319 OS << "'DDG' for loop '" << L.getHeader()->getName() << "':\n";320 OS << *AM.getResult<DDGAnalysis>(L, AR);321 return PreservedAnalyses::all();322}323