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 #include "llvm/SandboxIR/Instruction.h" 12 #include "llvm/SandboxIR/Utils.h" 13 14 namespace llvm::sandboxir { 15 16 PredIterator::value_type PredIterator::operator*() { 17 // If it's a DGNode then we dereference the operand iterator. 18 if (!isa<MemDGNode>(N)) { 19 assert(OpIt != OpItE && "Can't dereference end iterator!"); 20 return DAG->getNode(cast<Instruction>((Value *)*OpIt)); 21 } 22 // It's a MemDGNode, so we check if we return either the use-def operand, 23 // or a mem predecessor. 24 if (OpIt != OpItE) 25 return DAG->getNode(cast<Instruction>((Value *)*OpIt)); 26 assert(MemIt != cast<MemDGNode>(N)->memPreds().end() && 27 "Cant' dereference end iterator!"); 28 return *MemIt; 29 } 30 31 PredIterator &PredIterator::operator++() { 32 // If it's a DGNode then we increment the use-def iterator. 33 if (!isa<MemDGNode>(N)) { 34 assert(OpIt != OpItE && "Already at end!"); 35 ++OpIt; 36 // Skip operands that are not instructions. 37 OpIt = skipNonInstr(OpIt, OpItE); 38 return *this; 39 } 40 // It's a MemDGNode, so if we are not at the end of the use-def iterator we 41 // need to first increment that. 42 if (OpIt != OpItE) { 43 ++OpIt; 44 // Skip operands that are not instructions. 45 OpIt = skipNonInstr(OpIt, OpItE); 46 return *this; 47 } 48 assert(MemIt != cast<MemDGNode>(N)->memPreds().end() && "Already at end!"); 49 ++MemIt; 50 return *this; 51 } 52 53 bool PredIterator::operator==(const PredIterator &Other) const { 54 assert(DAG == Other.DAG && "Iterators of different DAGs!"); 55 assert(N == Other.N && "Iterators of different nodes!"); 56 return OpIt == Other.OpIt && MemIt == Other.MemIt; 57 } 58 59 #ifndef NDEBUG 60 void DGNode::print(raw_ostream &OS, bool PrintDeps) const { 61 I->dumpOS(OS); 62 if (PrintDeps) { 63 OS << "\n"; 64 // Print memory preds. 65 static constexpr const unsigned Indent = 4; 66 for (auto *Pred : MemPreds) { 67 OS.indent(Indent) << "<-"; 68 Pred->print(OS, false); 69 OS << "\n"; 70 } 71 } 72 } 73 void DGNode::dump() const { 74 print(dbgs()); 75 dbgs() << "\n"; 76 } 77 #endif // NDEBUG 78 79 Interval<MemDGNode> 80 MemDGNodeIntervalBuilder::make(const Interval<Instruction> &Instrs, 81 DependencyGraph &DAG) { 82 // If top or bottom instructions are not mem-dep candidate nodes we need to 83 // walk down/up the chain and find the mem-dep ones. 84 Instruction *MemTopI = Instrs.top(); 85 Instruction *MemBotI = Instrs.bottom(); 86 while (!DGNode::isMemDepNodeCandidate(MemTopI) && MemTopI != MemBotI) 87 MemTopI = MemTopI->getNextNode(); 88 while (!DGNode::isMemDepNodeCandidate(MemBotI) && MemBotI != MemTopI) 89 MemBotI = MemBotI->getPrevNode(); 90 // If we couldn't find a mem node in range TopN - BotN then it's empty. 91 if (!DGNode::isMemDepNodeCandidate(MemTopI)) 92 return {}; 93 // Now that we have the mem-dep nodes, create and return the range. 94 return Interval<MemDGNode>(cast<MemDGNode>(DAG.getNode(MemTopI)), 95 cast<MemDGNode>(DAG.getNode(MemBotI))); 96 } 97 98 DependencyGraph::DependencyType 99 DependencyGraph::getRoughDepType(Instruction *FromI, Instruction *ToI) { 100 // TODO: Perhaps compile-time improvement by skipping if neither is mem? 101 if (FromI->mayWriteToMemory()) { 102 if (ToI->mayReadFromMemory()) 103 return DependencyType::ReadAfterWrite; 104 if (ToI->mayWriteToMemory()) 105 return DependencyType::WriteAfterWrite; 106 } else if (FromI->mayReadFromMemory()) { 107 if (ToI->mayWriteToMemory()) 108 return DependencyType::WriteAfterRead; 109 } 110 if (isa<sandboxir::PHINode>(FromI) || isa<sandboxir::PHINode>(ToI)) 111 return DependencyType::Control; 112 if (ToI->isTerminator()) 113 return DependencyType::Control; 114 if (DGNode::isStackSaveOrRestoreIntrinsic(FromI) || 115 DGNode::isStackSaveOrRestoreIntrinsic(ToI)) 116 return DependencyType::Other; 117 return DependencyType::None; 118 } 119 120 static bool isOrdered(Instruction *I) { 121 auto IsOrdered = [](Instruction *I) { 122 if (auto *LI = dyn_cast<LoadInst>(I)) 123 return !LI->isUnordered(); 124 if (auto *SI = dyn_cast<StoreInst>(I)) 125 return !SI->isUnordered(); 126 if (DGNode::isFenceLike(I)) 127 return true; 128 return false; 129 }; 130 bool Is = IsOrdered(I); 131 assert((!Is || DGNode::isMemDepCandidate(I)) && 132 "An ordered instruction must be a MemDepCandidate!"); 133 return Is; 134 } 135 136 bool DependencyGraph::alias(Instruction *SrcI, Instruction *DstI, 137 DependencyType DepType) { 138 std::optional<MemoryLocation> DstLocOpt = 139 Utils::memoryLocationGetOrNone(DstI); 140 if (!DstLocOpt) 141 return true; 142 // Check aliasing. 143 assert((SrcI->mayReadFromMemory() || SrcI->mayWriteToMemory()) && 144 "Expected a mem instr"); 145 // TODO: Check AABudget 146 ModRefInfo SrcModRef = 147 isOrdered(SrcI) 148 ? ModRefInfo::ModRef 149 : Utils::aliasAnalysisGetModRefInfo(*BatchAA, SrcI, *DstLocOpt); 150 switch (DepType) { 151 case DependencyType::ReadAfterWrite: 152 case DependencyType::WriteAfterWrite: 153 return isModSet(SrcModRef); 154 case DependencyType::WriteAfterRead: 155 return isRefSet(SrcModRef); 156 default: 157 llvm_unreachable("Expected only RAW, WAW and WAR!"); 158 } 159 } 160 161 bool DependencyGraph::hasDep(Instruction *SrcI, Instruction *DstI) { 162 DependencyType RoughDepType = getRoughDepType(SrcI, DstI); 163 switch (RoughDepType) { 164 case DependencyType::ReadAfterWrite: 165 case DependencyType::WriteAfterWrite: 166 case DependencyType::WriteAfterRead: 167 return alias(SrcI, DstI, RoughDepType); 168 case DependencyType::Control: 169 // Adding actual dep edges from PHIs/to terminator would just create too 170 // many edges, which would be bad for compile-time. 171 // So we ignore them in the DAG formation but handle them in the 172 // scheduler, while sorting the ready list. 173 return false; 174 case DependencyType::Other: 175 return true; 176 case DependencyType::None: 177 return false; 178 } 179 llvm_unreachable("Unknown DependencyType enum"); 180 } 181 182 void DependencyGraph::scanAndAddDeps(DGNode &DstN, 183 const Interval<MemDGNode> &SrcScanRange) { 184 assert(isa<MemDGNode>(DstN) && 185 "DstN is the mem dep destination, so it must be mem"); 186 Instruction *DstI = DstN.getInstruction(); 187 // Walk up the instruction chain from ScanRange bottom to top, looking for 188 // memory instrs that may alias. 189 for (MemDGNode &SrcN : reverse(SrcScanRange)) { 190 Instruction *SrcI = SrcN.getInstruction(); 191 if (hasDep(SrcI, DstI)) 192 DstN.addMemPred(&SrcN); 193 } 194 } 195 196 Interval<Instruction> DependencyGraph::extend(ArrayRef<Instruction *> Instrs) { 197 if (Instrs.empty()) 198 return {}; 199 200 Interval<Instruction> InstrInterval(Instrs); 201 202 DGNode *LastN = getOrCreateNode(InstrInterval.top()); 203 // Create DGNodes for all instrs in Interval to avoid future Instruction to 204 // DGNode lookups. 205 MemDGNode *LastMemN = dyn_cast<MemDGNode>(LastN); 206 for (Instruction &I : drop_begin(InstrInterval)) { 207 auto *N = getOrCreateNode(&I); 208 // Build the Mem node chain. 209 if (auto *MemN = dyn_cast<MemDGNode>(N)) { 210 MemN->setPrevNode(LastMemN); 211 if (LastMemN != nullptr) 212 LastMemN->setNextNode(MemN); 213 LastMemN = MemN; 214 } 215 } 216 // Create the dependencies. 217 auto DstRange = MemDGNodeIntervalBuilder::make(InstrInterval, *this); 218 if (!DstRange.empty()) { 219 for (MemDGNode &DstN : drop_begin(DstRange)) { 220 auto SrcRange = Interval<MemDGNode>(DstRange.top(), DstN.getPrevNode()); 221 scanAndAddDeps(DstN, SrcRange); 222 } 223 } 224 225 return InstrInterval; 226 } 227 228 #ifndef NDEBUG 229 void DependencyGraph::print(raw_ostream &OS) const { 230 // InstrToNodeMap is unordered so we need to create an ordered vector. 231 SmallVector<DGNode *> Nodes; 232 Nodes.reserve(InstrToNodeMap.size()); 233 for (const auto &Pair : InstrToNodeMap) 234 Nodes.push_back(Pair.second.get()); 235 // Sort them based on which one comes first in the BB. 236 sort(Nodes, [](DGNode *N1, DGNode *N2) { 237 return N1->getInstruction()->comesBefore(N2->getInstruction()); 238 }); 239 for (auto *N : Nodes) 240 N->print(OS, /*PrintDeps=*/true); 241 } 242 243 void DependencyGraph::dump() const { 244 print(dbgs()); 245 dbgs() << "\n"; 246 } 247 #endif // NDEBUG 248 249 } // namespace llvm::sandboxir 250