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