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