1 //===- DependencyGraph.cpp ------------------------------------------===// 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 #include "llvm/Transforms/Vectorize/SandboxVectorizer/DependencyGraph.h" 10 #include "llvm/ADT/ArrayRef.h" 11 12 using namespace llvm::sandboxir; 13 14 #ifndef NDEBUG 15 void DGNode::print(raw_ostream &OS, bool PrintDeps) const { 16 I->dumpOS(OS); 17 if (PrintDeps) { 18 OS << "\n"; 19 // Print memory preds. 20 static constexpr const unsigned Indent = 4; 21 for (auto *Pred : MemPreds) { 22 OS.indent(Indent) << "<-"; 23 Pred->print(OS, false); 24 OS << "\n"; 25 } 26 } 27 } 28 void DGNode::dump() const { 29 print(dbgs()); 30 dbgs() << "\n"; 31 } 32 #endif // NDEBUG 33 34 Interval<MemDGNode> 35 MemDGNodeIntervalBuilder::make(const Interval<Instruction> &Instrs, 36 DependencyGraph &DAG) { 37 // If top or bottom instructions are not mem-dep candidate nodes we need to 38 // walk down/up the chain and find the mem-dep ones. 39 Instruction *MemTopI = Instrs.top(); 40 Instruction *MemBotI = Instrs.bottom(); 41 while (!DGNode::isMemDepCandidate(MemTopI) && MemTopI != MemBotI) 42 MemTopI = MemTopI->getNextNode(); 43 while (!DGNode::isMemDepCandidate(MemBotI) && MemBotI != MemTopI) 44 MemBotI = MemBotI->getPrevNode(); 45 // If we couldn't find a mem node in range TopN - BotN then it's empty. 46 if (!DGNode::isMemDepCandidate(MemTopI)) 47 return {}; 48 // Now that we have the mem-dep nodes, create and return the range. 49 return Interval<MemDGNode>(cast<MemDGNode>(DAG.getNode(MemTopI)), 50 cast<MemDGNode>(DAG.getNode(MemBotI))); 51 } 52 53 Interval<Instruction> DependencyGraph::extend(ArrayRef<Instruction *> Instrs) { 54 if (Instrs.empty()) 55 return {}; 56 // TODO: For now create a chain of dependencies. 57 Interval<Instruction> Interval(Instrs); 58 auto *TopI = Interval.top(); 59 auto *BotI = Interval.bottom(); 60 DGNode *LastN = getOrCreateNode(TopI); 61 MemDGNode *LastMemN = dyn_cast<MemDGNode>(LastN); 62 for (Instruction *I = TopI->getNextNode(), *E = BotI->getNextNode(); I != E; 63 I = I->getNextNode()) { 64 auto *N = getOrCreateNode(I); 65 N->addMemPred(LastMemN); 66 // Build the Mem node chain. 67 if (auto *MemN = dyn_cast<MemDGNode>(N)) { 68 MemN->setPrevNode(LastMemN); 69 if (LastMemN != nullptr) 70 LastMemN->setNextNode(MemN); 71 LastMemN = MemN; 72 } 73 LastN = N; 74 } 75 return Interval; 76 } 77 78 #ifndef NDEBUG 79 void DependencyGraph::print(raw_ostream &OS) const { 80 // InstrToNodeMap is unordered so we need to create an ordered vector. 81 SmallVector<DGNode *> Nodes; 82 Nodes.reserve(InstrToNodeMap.size()); 83 for (const auto &Pair : InstrToNodeMap) 84 Nodes.push_back(Pair.second.get()); 85 // Sort them based on which one comes first in the BB. 86 sort(Nodes, [](DGNode *N1, DGNode *N2) { 87 return N1->getInstruction()->comesBefore(N2->getInstruction()); 88 }); 89 for (auto *N : Nodes) 90 N->print(OS, /*PrintDeps=*/true); 91 } 92 93 void DependencyGraph::dump() const { 94 print(dbgs()); 95 dbgs() << "\n"; 96 } 97 #endif // NDEBUG 98