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 } 66 if (isa<sandboxir::PHINode>(FromI) || isa<sandboxir::PHINode>(ToI)) 67 return DependencyType::Control; 68 if (ToI->isTerminator()) 69 return DependencyType::Control; 70 if (DGNode::isStackSaveOrRestoreIntrinsic(FromI) || 71 DGNode::isStackSaveOrRestoreIntrinsic(ToI)) 72 return DependencyType::Other; 73 return DependencyType::None; 74 } 75 76 static bool isOrdered(Instruction *I) { 77 auto IsOrdered = [](Instruction *I) { 78 if (auto *LI = dyn_cast<LoadInst>(I)) 79 return !LI->isUnordered(); 80 if (auto *SI = dyn_cast<StoreInst>(I)) 81 return !SI->isUnordered(); 82 if (DGNode::isFenceLike(I)) 83 return true; 84 return false; 85 }; 86 bool Is = IsOrdered(I); 87 assert((!Is || DGNode::isMemDepCandidate(I)) && 88 "An ordered instruction must be a MemDepCandidate!"); 89 return Is; 90 } 91 92 bool DependencyGraph::alias(Instruction *SrcI, Instruction *DstI, 93 DependencyType DepType) { 94 std::optional<MemoryLocation> DstLocOpt = 95 Utils::memoryLocationGetOrNone(DstI); 96 if (!DstLocOpt) 97 return true; 98 // Check aliasing. 99 assert((SrcI->mayReadFromMemory() || SrcI->mayWriteToMemory()) && 100 "Expected a mem instr"); 101 // TODO: Check AABudget 102 ModRefInfo SrcModRef = 103 isOrdered(SrcI) 104 ? ModRefInfo::ModRef 105 : Utils::aliasAnalysisGetModRefInfo(*BatchAA, SrcI, *DstLocOpt); 106 switch (DepType) { 107 case DependencyType::ReadAfterWrite: 108 case DependencyType::WriteAfterWrite: 109 return isModSet(SrcModRef); 110 case DependencyType::WriteAfterRead: 111 return isRefSet(SrcModRef); 112 default: 113 llvm_unreachable("Expected only RAW, WAW and WAR!"); 114 } 115 } 116 117 bool DependencyGraph::hasDep(Instruction *SrcI, Instruction *DstI) { 118 DependencyType RoughDepType = getRoughDepType(SrcI, DstI); 119 switch (RoughDepType) { 120 case DependencyType::ReadAfterWrite: 121 case DependencyType::WriteAfterWrite: 122 case DependencyType::WriteAfterRead: 123 return alias(SrcI, DstI, RoughDepType); 124 case DependencyType::Control: 125 // Adding actual dep edges from PHIs/to terminator would just create too 126 // many edges, which would be bad for compile-time. 127 // So we ignore them in the DAG formation but handle them in the 128 // scheduler, while sorting the ready list. 129 return false; 130 case DependencyType::Other: 131 return true; 132 case DependencyType::None: 133 return false; 134 } 135 llvm_unreachable("Unknown DependencyType enum"); 136 } 137 138 void DependencyGraph::scanAndAddDeps(DGNode &DstN, 139 const Interval<MemDGNode> &SrcScanRange) { 140 assert(isa<MemDGNode>(DstN) && 141 "DstN is the mem dep destination, so it must be mem"); 142 Instruction *DstI = DstN.getInstruction(); 143 // Walk up the instruction chain from ScanRange bottom to top, looking for 144 // memory instrs that may alias. 145 for (MemDGNode &SrcN : reverse(SrcScanRange)) { 146 Instruction *SrcI = SrcN.getInstruction(); 147 if (hasDep(SrcI, DstI)) 148 DstN.addMemPred(&SrcN); 149 } 150 } 151 152 Interval<Instruction> DependencyGraph::extend(ArrayRef<Instruction *> Instrs) { 153 if (Instrs.empty()) 154 return {}; 155 156 Interval<Instruction> InstrInterval(Instrs); 157 158 DGNode *LastN = getOrCreateNode(InstrInterval.top()); 159 // Create DGNodes for all instrs in Interval to avoid future Instruction to 160 // DGNode lookups. 161 MemDGNode *LastMemN = dyn_cast<MemDGNode>(LastN); 162 for (Instruction &I : drop_begin(InstrInterval)) { 163 auto *N = getOrCreateNode(&I); 164 // Build the Mem node chain. 165 if (auto *MemN = dyn_cast<MemDGNode>(N)) { 166 MemN->setPrevNode(LastMemN); 167 if (LastMemN != nullptr) 168 LastMemN->setNextNode(MemN); 169 LastMemN = MemN; 170 } 171 } 172 // Create the dependencies. 173 auto DstRange = MemDGNodeIntervalBuilder::make(InstrInterval, *this); 174 if (!DstRange.empty()) { 175 for (MemDGNode &DstN : drop_begin(DstRange)) { 176 auto SrcRange = Interval<MemDGNode>(DstRange.top(), DstN.getPrevNode()); 177 scanAndAddDeps(DstN, SrcRange); 178 } 179 } 180 181 return InstrInterval; 182 } 183 184 #ifndef NDEBUG 185 void DependencyGraph::print(raw_ostream &OS) const { 186 // InstrToNodeMap is unordered so we need to create an ordered vector. 187 SmallVector<DGNode *> Nodes; 188 Nodes.reserve(InstrToNodeMap.size()); 189 for (const auto &Pair : InstrToNodeMap) 190 Nodes.push_back(Pair.second.get()); 191 // Sort them based on which one comes first in the BB. 192 sort(Nodes, [](DGNode *N1, DGNode *N2) { 193 return N1->getInstruction()->comesBefore(N2->getInstruction()); 194 }); 195 for (auto *N : Nodes) 196 N->print(OS, /*PrintDeps=*/true); 197 } 198 199 void DependencyGraph::dump() const { 200 print(dbgs()); 201 dbgs() << "\n"; 202 } 203 #endif // NDEBUG 204 205 } // namespace llvm::sandboxir 206