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