llvm/lib/MCA/Instruction.cpp

   1 //===--------------------- Instruction.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 //
   9 // This file defines abstractions used by the Pipeline to model register reads,
  10 // register writes and instructions.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/MCA/Instruction.h"
  15 #include "llvm/Support/Debug.h"
  16 #include "llvm/Support/raw_ostream.h"
  17
  18 namespace llvm {
  19 namespace mca {
  20
  21 void WriteState::writeStartEvent(unsigned IID, MCPhysReg RegID,
  22                                  unsigned Cycles) {
  23   CRD.IID = IID;
  24   CRD.RegID = RegID;
  25   CRD.Cycles = Cycles;
  26   DependentWriteCyclesLeft = Cycles;
  27   DependentWrite = nullptr;
  28 }
  29
  30 void ReadState::writeStartEvent(unsigned IID, MCPhysReg RegID,
  31                                 unsigned Cycles) {
  32   assert(DependentWrites);
  33   assert(CyclesLeft == UNKNOWN_CYCLES);
  34
  35   // This read may be dependent on more than one write. This typically occurs
  36   // when a definition is the result of multiple writes where at least one
  37   // write does a partial register update.
  38   // The HW is forced to do some extra bookkeeping to track of all the
  39   // dependent writes, and implement a merging scheme for the partial writes.
  40   --DependentWrites;
  41   if (TotalCycles < Cycles) {
  42     CRD.IID = IID;
  43     CRD.RegID = RegID;
  44     CRD.Cycles = Cycles;
  45     TotalCycles = Cycles;
  46   }
  47
  48   if (!DependentWrites) {
  49     CyclesLeft = TotalCycles;
  50     IsReady = !CyclesLeft;
  51   }
  52 }
  53
  54 void WriteState::onInstructionIssued(unsigned IID) {
  55   assert(CyclesLeft == UNKNOWN_CYCLES);
  56   // Update the number of cycles left based on the WriteDescriptor info.
  57   CyclesLeft = getLatency();
  58
  59   // Now that the time left before write-back is known, notify
  60   // all the users.
  61   for (const std::pair<ReadState *, int> &User : Users) {
  62     ReadState *RS = User.first;
  63     unsigned ReadCycles = std::max(0, CyclesLeft - User.second);
  64     RS->writeStartEvent(IID, RegisterID, ReadCycles);
  65   }
  66
  67   // Notify any writes that are in a false dependency with this write.
  68   if (PartialWrite)
  69     PartialWrite->writeStartEvent(IID, RegisterID, CyclesLeft);
  70 }
  71
  72 void WriteState::addUser(unsigned IID, ReadState *User, int ReadAdvance) {
  73   // If CyclesLeft is different than -1, then we don't need to
  74   // update the list of users. We can just notify the user with
  75   // the actual number of cycles left (which may be zero).
  76   if (CyclesLeft != UNKNOWN_CYCLES) {
  77     unsigned ReadCycles = std::max(0, CyclesLeft - ReadAdvance);
  78     User->writeStartEvent(IID, RegisterID, ReadCycles);
  79     return;
  80   }
  81
  82   Users.emplace_back(User, ReadAdvance);
  83 }
  84
  85 void WriteState::addUser(unsigned IID, WriteState *User) {
  86   if (CyclesLeft != UNKNOWN_CYCLES) {
  87     User->writeStartEvent(IID, RegisterID, std::max(0, CyclesLeft));
  88     return;
  89   }
  90
  91   assert(!PartialWrite && "PartialWrite already set!");
  92   PartialWrite = User;
  93   User->setDependentWrite(this);
  94 }
  95
  96 void WriteState::cycleEvent() {
  97   // Note: CyclesLeft can be a negative number. It is an error to
  98   // make it an unsigned quantity because users of this write may
  99   // specify a negative ReadAdvance.
 100   if (CyclesLeft != UNKNOWN_CYCLES)
 101     CyclesLeft--;
 102
 103   if (DependentWriteCyclesLeft)
 104     DependentWriteCyclesLeft--;
 105 }
 106
 107 void ReadState::cycleEvent() {
 108   // Update the total number of cycles.
 109   if (DependentWrites && TotalCycles) {
 110     --TotalCycles;
 111     return;
 112   }
 113
 114   // Bail out immediately if we don't know how many cycles are left.
 115   if (CyclesLeft == UNKNOWN_CYCLES)
 116     return;
 117
 118   if (CyclesLeft) {
 119     --CyclesLeft;
 120     IsReady = !CyclesLeft;
 121   }
 122 }
 123
 124 #ifndef NDEBUG
 125 void WriteState::dump() const {
 126   dbgs() << "{ OpIdx=" << WD->OpIndex << ", Lat=" << getLatency() << ", RegID "
 127          << getRegisterID() << ", Cycles Left=" << getCyclesLeft() << " }";
 128 }
 129 #endif
 130
 131 const CriticalDependency &Instruction::computeCriticalRegDep() {
 132   if (CriticalRegDep.Cycles)
 133     return CriticalRegDep;
 134
 135   unsigned MaxLatency = 0;
 136   for (const WriteState &WS : getDefs()) {
 137     const CriticalDependency &WriteCRD = WS.getCriticalRegDep();
 138     if (WriteCRD.Cycles > MaxLatency)
 139       CriticalRegDep = WriteCRD;
 140   }
 141
 142   for (const ReadState &RS : getUses()) {
 143     const CriticalDependency &ReadCRD = RS.getCriticalRegDep();
 144     if (ReadCRD.Cycles > MaxLatency)
 145       CriticalRegDep = ReadCRD;
 146   }
 147
 148   return CriticalRegDep;
 149 }
 150
 151 void Instruction::reset() {
 152   // Note that this won't clear read/write descriptors
 153   // or other non-trivial fields
 154   Stage = IS_INVALID;
 155   CyclesLeft = UNKNOWN_CYCLES;
 156   clearOptimizableMove();
 157   RCUTokenID = 0;
 158   LSUTokenID = 0;
 159   CriticalResourceMask = 0;
 160   IsEliminated = false;
 161 }
 162
 163 void Instruction::dispatch(unsigned RCUToken) {
 164   assert(Stage == IS_INVALID);
 165   Stage = IS_DISPATCHED;
 166   RCUTokenID = RCUToken;
 167
 168   // Check if input operands are already available.
 169   if (updateDispatched())
 170     updatePending();
 171 }
 172
 173 void Instruction::execute(unsigned IID) {
 174   assert(Stage == IS_READY);
 175   Stage = IS_EXECUTING;
 176
 177   // Set the cycles left before the write-back stage.
 178   CyclesLeft = getLatency();
 179
 180   for (WriteState &WS : getDefs())
 181     WS.onInstructionIssued(IID);
 182
 183   // Transition to the "executed" stage if this is a zero-latency instruction.
 184   if (!CyclesLeft)
 185     Stage = IS_EXECUTED;
 186 }
 187
 188 void Instruction::forceExecuted() {
 189   assert(Stage == IS_READY && "Invalid internal state!");
 190   CyclesLeft = 0;
 191   Stage = IS_EXECUTED;
 192 }
 193
 194 bool Instruction::updatePending() {
 195   assert(isPending() && "Unexpected instruction stage found!");
 196
 197   if (!all_of(getUses(), [](const ReadState &Use) { return Use.isReady(); }))
 198     return false;
 199
 200   // A partial register write cannot complete before a dependent write.
 201   if (!all_of(getDefs(), [](const WriteState &Def) { return Def.isReady(); }))
 202     return false;
 203
 204   Stage = IS_READY;
 205   return true;
 206 }
 207
 208 bool Instruction::updateDispatched() {
 209   assert(isDispatched() && "Unexpected instruction stage found!");
 210
 211   if (!all_of(getUses(), [](const ReadState &Use) {
 212         return Use.isPending() || Use.isReady();
 213       }))
 214     return false;
 215
 216   // A partial register write cannot complete before a dependent write.
 217   if (!all_of(getDefs(),
 218               [](const WriteState &Def) { return !Def.getDependentWrite(); }))
 219     return false;
 220
 221   Stage = IS_PENDING;
 222   return true;
 223 }
 224
 225 void Instruction::update() {
 226   if (isDispatched())
 227     updateDispatched();
 228   if (isPending())
 229     updatePending();
 230 }
 231
 232 void Instruction::cycleEvent() {
 233   if (isReady())
 234     return;
 235
 236   if (isDispatched() || isPending()) {
 237     for (ReadState &Use : getUses())
 238       Use.cycleEvent();
 239
 240     for (WriteState &Def : getDefs())
 241       Def.cycleEvent();
 242
 243     update();
 244     return;
 245   }
 246
 247   assert(isExecuting() && "Instruction not in-flight?");
 248   assert(CyclesLeft && "Instruction already executed?");
 249   for (WriteState &Def : getDefs())
 250     Def.cycleEvent();
 251   CyclesLeft--;
 252   if (!CyclesLeft)
 253     Stage = IS_EXECUTED;
 254 }
 255
 256 } // namespace mca
 257 } // namespace llvm