llvm/lib/MCA/Stages/InOrderIssueStage.cpp

   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