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