1 //===---------------------- InOrderIssueStage.cpp ---------------*- C++ -*-===// 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 /// \file 9 /// 10 /// InOrderIssueStage implements an in-order execution pipeline. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/MCA/Stages/InOrderIssueStage.h" 15 #include "llvm/MCA/HardwareUnits/LSUnit.h" 16 #include "llvm/MCA/HardwareUnits/RegisterFile.h" 17 #include "llvm/MCA/HardwareUnits/RetireControlUnit.h" 18 #include "llvm/MCA/Instruction.h" 19 20 #define DEBUG_TYPE "llvm-mca" 21 namespace llvm { 22 namespace mca { 23 24 void StallInfo::clear() { 25 IR.invalidate(); 26 CyclesLeft = 0; 27 Kind = StallKind::DEFAULT; 28 } 29 30 void StallInfo::update(const InstRef &Inst, unsigned Cycles, StallKind SK) { 31 IR = Inst; 32 CyclesLeft = Cycles; 33 Kind = SK; 34 } 35 36 void StallInfo::cycleEnd() { 37 if (!isValid()) 38 return; 39 40 if (!CyclesLeft) 41 return; 42 43 --CyclesLeft; 44 } 45 46 InOrderIssueStage::InOrderIssueStage(const MCSubtargetInfo &STI, 47 RegisterFile &PRF, CustomBehaviour &CB, 48 LSUnit &LSU) 49 : STI(STI), PRF(PRF), RM(STI.getSchedModel()), CB(CB), LSU(LSU), 50 NumIssued(), CarryOver(), Bandwidth(), LastWriteBackCycle() {} 51 52 unsigned InOrderIssueStage::getIssueWidth() const { 53 return STI.getSchedModel().IssueWidth; 54 } 55 56 bool InOrderIssueStage::hasWorkToComplete() const { 57 return !IssuedInst.empty() || SI.isValid() || CarriedOver; 58 } 59 60 bool InOrderIssueStage::isAvailable(const InstRef &IR) const { 61 if (SI.isValid() || CarriedOver) 62 return false; 63 64 const Instruction &Inst = *IR.getInstruction(); 65 unsigned NumMicroOps = Inst.getNumMicroOps(); 66 67 bool ShouldCarryOver = NumMicroOps > getIssueWidth(); 68 if (Bandwidth < NumMicroOps && !ShouldCarryOver) 69 return false; 70 71 // Instruction with BeginGroup must be the first instruction to be issued in a 72 // cycle. 73 if (Inst.getBeginGroup() && NumIssued != 0) 74 return false; 75 76 return true; 77 } 78 79 static bool hasResourceHazard(const ResourceManager &RM, const InstRef &IR) { 80 if (RM.checkAvailability(IR.getInstruction()->getDesc())) { 81 LLVM_DEBUG(dbgs() << "[E] Stall #" << IR << '\n'); 82 return true; 83 } 84 85 return false; 86 } 87 88 static unsigned findFirstWriteBackCycle(const InstRef &IR) { 89 unsigned FirstWBCycle = IR.getInstruction()->getLatency(); 90 for (const WriteState &WS : IR.getInstruction()->getDefs()) { 91 int CyclesLeft = WS.getCyclesLeft(); 92 if (CyclesLeft == UNKNOWN_CYCLES) 93 CyclesLeft = WS.getLatency(); 94 if (CyclesLeft < 0) 95 CyclesLeft = 0; 96 FirstWBCycle = std::min(FirstWBCycle, (unsigned)CyclesLeft); 97 } 98 return FirstWBCycle; 99 } 100 101 /// Return a number of cycles left until register requirements of the 102 /// instructions are met. 103 static unsigned checkRegisterHazard(const RegisterFile &PRF, 104 const MCSubtargetInfo &STI, 105 const InstRef &IR) { 106 for (const ReadState &RS : IR.getInstruction()->getUses()) { 107 RegisterFile::RAWHazard Hazard = PRF.checkRAWHazards(STI, RS); 108 if (Hazard.isValid()) 109 return Hazard.hasUnknownCycles() ? 1U : Hazard.CyclesLeft; 110 } 111 112 return 0; 113 } 114 115 bool InOrderIssueStage::canExecute(const InstRef &IR) { 116 assert(!SI.getCyclesLeft() && "Should not have reached this code!"); 117 assert(!SI.isValid() && "Should not have reached this code!"); 118 119 if (unsigned Cycles = checkRegisterHazard(PRF, STI, IR)) { 120 SI.update(IR, Cycles, StallInfo::StallKind::REGISTER_DEPS); 121 return false; 122 } 123 124 if (hasResourceHazard(RM, IR)) { 125 SI.update(IR, /* delay */ 1, StallInfo::StallKind::DISPATCH); 126 return false; 127 } 128 129 if (IR.getInstruction()->isMemOp() && !LSU.isReady(IR)) { 130 // This load (store) aliases with a preceding store (load). Delay 131 // it until the depenency is cleared. 132 SI.update(IR, /* delay */ 1, StallInfo::StallKind::LOAD_STORE); 133 return false; 134 } 135 136 if (unsigned CustomStallCycles = CB.checkCustomHazard(IssuedInst, IR)) { 137 SI.update(IR, CustomStallCycles, StallInfo::StallKind::CUSTOM_STALL); 138 return false; 139 } 140 141 if (LastWriteBackCycle) { 142 if (!IR.getInstruction()->getRetireOOO()) { 143 unsigned NextWriteBackCycle = findFirstWriteBackCycle(IR); 144 // Delay the instruction to ensure that writes happen in program order. 145 if (NextWriteBackCycle < LastWriteBackCycle) { 146 SI.update(IR, LastWriteBackCycle - NextWriteBackCycle, 147 StallInfo::StallKind::DELAY); 148 return false; 149 } 150 } 151 } 152 153 return true; 154 } 155 156 static void addRegisterReadWrite(RegisterFile &PRF, Instruction &IS, 157 unsigned SourceIndex, 158 const MCSubtargetInfo &STI, 159 SmallVectorImpl<unsigned> &UsedRegs) { 160 assert(!IS.isEliminated()); 161 162 for (ReadState &RS : IS.getUses()) 163 PRF.addRegisterRead(RS, STI); 164 165 for (WriteState &WS : IS.getDefs()) 166 PRF.addRegisterWrite(WriteRef(SourceIndex, &WS), UsedRegs); 167 } 168 169 void InOrderIssueStage::notifyInstructionIssued(const InstRef &IR, 170 ArrayRef<ResourceUse> UsedRes) { 171 notifyEvent<HWInstructionEvent>( 172 HWInstructionEvent(HWInstructionEvent::Ready, IR)); 173 notifyEvent<HWInstructionEvent>(HWInstructionIssuedEvent(IR, UsedRes)); 174 175 LLVM_DEBUG(dbgs() << "[E] Issued #" << IR << "\n"); 176 } 177 178 void InOrderIssueStage::notifyInstructionDispatched( 179 const InstRef &IR, unsigned Ops, ArrayRef<unsigned> UsedRegs) { 180 notifyEvent<HWInstructionEvent>( 181 HWInstructionDispatchedEvent(IR, UsedRegs, Ops)); 182 183 LLVM_DEBUG(dbgs() << "[E] Dispatched #" << IR << "\n"); 184 } 185 186 void InOrderIssueStage::notifyInstructionExecuted(const InstRef &IR) { 187 notifyEvent<HWInstructionEvent>( 188 HWInstructionEvent(HWInstructionEvent::Executed, IR)); 189 LLVM_DEBUG(dbgs() << "[E] Instruction #" << IR << " is executed\n"); 190 } 191 192 void InOrderIssueStage::notifyInstructionRetired(const InstRef &IR, 193 ArrayRef<unsigned> FreedRegs) { 194 notifyEvent<HWInstructionEvent>(HWInstructionRetiredEvent(IR, FreedRegs)); 195 LLVM_DEBUG(dbgs() << "[E] Retired #" << IR << " \n"); 196 } 197 198 llvm::Error InOrderIssueStage::execute(InstRef &IR) { 199 Instruction &IS = *IR.getInstruction(); 200 if (IS.isMemOp()) 201 IS.setLSUTokenID(LSU.dispatch(IR)); 202 203 if (llvm::Error E = tryIssue(IR)) 204 return E; 205 206 if (SI.isValid()) 207 notifyStallEvent(); 208 209 return llvm::ErrorSuccess(); 210 } 211 212 llvm::Error InOrderIssueStage::tryIssue(InstRef &IR) { 213 Instruction &IS = *IR.getInstruction(); 214 unsigned SourceIndex = IR.getSourceIndex(); 215 const InstrDesc &Desc = IS.getDesc(); 216 217 if (!canExecute(IR)) { 218 LLVM_DEBUG(dbgs() << "[N] Stalled #" << SI.getInstruction() << " for " 219 << SI.getCyclesLeft() << " cycles\n"); 220 Bandwidth = 0; 221 return llvm::ErrorSuccess(); 222 } 223 224 unsigned RCUTokenID = RetireControlUnit::UnhandledTokenID; 225 IS.dispatch(RCUTokenID); 226 227 SmallVector<unsigned, 4> UsedRegs(PRF.getNumRegisterFiles()); 228 addRegisterReadWrite(PRF, IS, SourceIndex, STI, UsedRegs); 229 230 unsigned NumMicroOps = IS.getNumMicroOps(); 231 notifyInstructionDispatched(IR, NumMicroOps, UsedRegs); 232 233 SmallVector<ResourceUse, 4> UsedResources; 234 RM.issueInstruction(Desc, UsedResources); 235 IS.execute(SourceIndex); 236 237 if (IS.isMemOp()) 238 LSU.onInstructionIssued(IR); 239 240 // Replace resource masks with valid resource processor IDs. 241 for (ResourceUse &Use : UsedResources) { 242 uint64_t Mask = Use.first.first; 243 Use.first.first = RM.resolveResourceMask(Mask); 244 } 245 notifyInstructionIssued(IR, UsedResources); 246 247 bool ShouldCarryOver = NumMicroOps > Bandwidth; 248 if (ShouldCarryOver) { 249 CarryOver = NumMicroOps - Bandwidth; 250 CarriedOver = IR; 251 Bandwidth = 0; 252 NumIssued += Bandwidth; 253 LLVM_DEBUG(dbgs() << "[N] Carry over #" << IR << " \n"); 254 } else { 255 NumIssued += NumMicroOps; 256 Bandwidth = IS.getEndGroup() ? 0 : Bandwidth - NumMicroOps; 257 } 258 259 // If the instruction has a latency of 0, we need to handle 260 // the execution and retirement now. 261 if (IS.isExecuted()) { 262 PRF.onInstructionExecuted(&IS); 263 LSU.onInstructionExecuted(IR); 264 notifyEvent<HWInstructionEvent>( 265 HWInstructionEvent(HWInstructionEvent::Executed, IR)); 266 LLVM_DEBUG(dbgs() << "[E] Instruction #" << IR << " is executed\n"); 267 268 retireInstruction(IR); 269 return llvm::ErrorSuccess(); 270 } 271 272 IssuedInst.push_back(IR); 273 274 if (!IR.getInstruction()->getRetireOOO()) 275 LastWriteBackCycle = IS.getCyclesLeft(); 276 277 return llvm::ErrorSuccess(); 278 } 279 280 void InOrderIssueStage::updateIssuedInst() { 281 // Update other instructions. Executed instructions will be retired during the 282 // next cycle. 283 unsigned NumExecuted = 0; 284 for (auto I = IssuedInst.begin(), E = IssuedInst.end(); 285 I != (E - NumExecuted);) { 286 InstRef &IR = *I; 287 Instruction &IS = *IR.getInstruction(); 288 289 IS.cycleEvent(); 290 if (!IS.isExecuted()) { 291 LLVM_DEBUG(dbgs() << "[N] Instruction #" << IR 292 << " is still executing\n"); 293 ++I; 294 continue; 295 } 296 297 PRF.onInstructionExecuted(&IS); 298 LSU.onInstructionExecuted(IR); 299 notifyInstructionExecuted(IR); 300 ++NumExecuted; 301 302 retireInstruction(*I); 303 304 std::iter_swap(I, E - NumExecuted); 305 } 306 307 if (NumExecuted) 308 IssuedInst.resize(IssuedInst.size() - NumExecuted); 309 } 310 311 void InOrderIssueStage::updateCarriedOver() { 312 if (!CarriedOver) 313 return; 314 315 assert(!SI.isValid() && "A stalled instruction cannot be carried over."); 316 317 if (CarryOver > Bandwidth) { 318 CarryOver -= Bandwidth; 319 Bandwidth = 0; 320 LLVM_DEBUG(dbgs() << "[N] Carry over (" << CarryOver << "uops left) #" 321 << CarriedOver << " \n"); 322 return; 323 } 324 325 LLVM_DEBUG(dbgs() << "[N] Carry over (complete) #" << CarriedOver << " \n"); 326 327 if (CarriedOver.getInstruction()->getEndGroup()) 328 Bandwidth = 0; 329 else 330 Bandwidth -= CarryOver; 331 332 CarriedOver = InstRef(); 333 CarryOver = 0; 334 } 335 336 void InOrderIssueStage::retireInstruction(InstRef &IR) { 337 Instruction &IS = *IR.getInstruction(); 338 IS.retire(); 339 340 llvm::SmallVector<unsigned, 4> FreedRegs(PRF.getNumRegisterFiles()); 341 for (const WriteState &WS : IS.getDefs()) 342 PRF.removeRegisterWrite(WS, FreedRegs); 343 344 if (IS.isMemOp()) 345 LSU.onInstructionRetired(IR); 346 347 notifyInstructionRetired(IR, FreedRegs); 348 } 349 350 void InOrderIssueStage::notifyStallEvent() { 351 assert(SI.getCyclesLeft() && "A zero cycles stall?"); 352 assert(SI.isValid() && "Invalid stall information found!"); 353 354 const InstRef &IR = SI.getInstruction(); 355 356 switch (SI.getStallKind()) { 357 default: 358 break; 359 case StallInfo::StallKind::REGISTER_DEPS: { 360 notifyEvent<HWStallEvent>( 361 HWStallEvent(HWStallEvent::RegisterFileStall, IR)); 362 notifyEvent<HWPressureEvent>( 363 HWPressureEvent(HWPressureEvent::REGISTER_DEPS, IR)); 364 break; 365 } 366 case StallInfo::StallKind::DISPATCH: { 367 notifyEvent<HWStallEvent>( 368 HWStallEvent(HWStallEvent::DispatchGroupStall, IR)); 369 notifyEvent<HWPressureEvent>( 370 HWPressureEvent(HWPressureEvent::RESOURCES, IR)); 371 break; 372 } 373 case StallInfo::StallKind::CUSTOM_STALL: { 374 notifyEvent<HWStallEvent>( 375 HWStallEvent(HWStallEvent::CustomBehaviourStall, IR)); 376 break; 377 } 378 } 379 } 380 381 llvm::Error InOrderIssueStage::cycleStart() { 382 NumIssued = 0; 383 Bandwidth = getIssueWidth(); 384 385 PRF.cycleStart(); 386 LSU.cycleEvent(); 387 388 // Release consumed resources. 389 SmallVector<ResourceRef, 4> Freed; 390 RM.cycleEvent(Freed); 391 392 updateIssuedInst(); 393 394 // Continue to issue the instruction carried over from the previous cycle 395 updateCarriedOver(); 396 397 // Issue instructions scheduled for this cycle 398 if (SI.isValid()) { 399 if (!SI.getCyclesLeft()) { 400 // Make a copy of the reference, and try issue it again. 401 // Do not take the instruction reference because SI.clear() will 402 // invalidate it. 403 InstRef IR = SI.getInstruction(); 404 SI.clear(); 405 406 if (llvm::Error E = tryIssue(IR)) 407 return E; 408 } 409 410 if (SI.getCyclesLeft()) { 411 // The instruction is still stalled, cannot issue any new instructions in 412 // this cycle. 413 notifyStallEvent(); 414 Bandwidth = 0; 415 return llvm::ErrorSuccess(); 416 } 417 } 418 419 assert((NumIssued <= getIssueWidth()) && "Overflow."); 420 return llvm::ErrorSuccess(); 421 } 422 423 llvm::Error InOrderIssueStage::cycleEnd() { 424 PRF.cycleEnd(); 425 SI.cycleEnd(); 426 427 if (LastWriteBackCycle > 0) 428 --LastWriteBackCycle; 429 430 return llvm::ErrorSuccess(); 431 } 432 433 } // namespace mca 434 } // namespace llvm 435