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