Home | History | Annotate | Download | only in llvm-mca 
      1 //===--------------------- Instruction.cpp ----------------------*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This file defines abstractions used by the Pipeline to model register reads,
     11 // register writes and instructions.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #include "Instruction.h"
     16 #include "llvm/Support/Debug.h"
     17 #include "llvm/Support/raw_ostream.h"
     18 
     19 namespace mca {
     20 
     21 using namespace llvm;
     22 
     23 void ReadState::writeStartEvent(unsigned Cycles) {
     24   assert(DependentWrites);
     25   assert(CyclesLeft == UNKNOWN_CYCLES);
     26 
     27   // This read may be dependent on more than one write. This typically occurs
     28   // when a definition is the result of multiple writes where at least one
     29   // write does a partial register update.
     30   // The HW is forced to do some extra bookkeeping to track of all the
     31   // dependent writes, and implement a merging scheme for the partial writes.
     32   --DependentWrites;
     33   TotalCycles = std::max(TotalCycles, Cycles);
     34 
     35   if (!DependentWrites) {
     36     CyclesLeft = TotalCycles;
     37     IsReady = !CyclesLeft;
     38   }
     39 }
     40 
     41 void WriteState::onInstructionIssued() {
     42   assert(CyclesLeft == UNKNOWN_CYCLES);
     43   // Update the number of cycles left based on the WriteDescriptor info.
     44   CyclesLeft = getLatency();
     45 
     46   // Now that the time left before write-back is known, notify
     47   // all the users.
     48   for (const std::pair<ReadState *, int> &User : Users) {
     49     ReadState *RS = User.first;
     50     unsigned ReadCycles = std::max(0, CyclesLeft - User.second);
     51     RS->writeStartEvent(ReadCycles);
     52   }
     53 }
     54 
     55 void WriteState::addUser(ReadState *User, int ReadAdvance) {
     56   // If CyclesLeft is different than -1, then we don't need to
     57   // update the list of users. We can just notify the user with
     58   // the actual number of cycles left (which may be zero).
     59   if (CyclesLeft != UNKNOWN_CYCLES) {
     60     unsigned ReadCycles = std::max(0, CyclesLeft - ReadAdvance);
     61     User->writeStartEvent(ReadCycles);
     62     return;
     63   }
     64 
     65   std::pair<ReadState *, int> NewPair(User, ReadAdvance);
     66   Users.insert(NewPair);
     67 }
     68 
     69 void WriteState::cycleEvent() {
     70   // Note: CyclesLeft can be a negative number. It is an error to
     71   // make it an unsigned quantity because users of this write may
     72   // specify a negative ReadAdvance.
     73   if (CyclesLeft != UNKNOWN_CYCLES)
     74     CyclesLeft--;
     75 }
     76 
     77 void ReadState::cycleEvent() {
     78   // Update the total number of cycles.
     79   if (DependentWrites && TotalCycles) {
     80     --TotalCycles;
     81     return;
     82   }
     83 
     84   // Bail out immediately if we don't know how many cycles are left.
     85   if (CyclesLeft == UNKNOWN_CYCLES)
     86     return;
     87 
     88   if (CyclesLeft) {
     89     --CyclesLeft;
     90     IsReady = !CyclesLeft;
     91   }
     92 }
     93 
     94 #ifndef NDEBUG
     95 void WriteState::dump() const {
     96   dbgs() << "{ OpIdx=" << WD.OpIndex << ", Lat=" << getLatency() << ", RegID "
     97          << getRegisterID() << ", Cycles Left=" << getCyclesLeft() << " }";
     98 }
     99 
    100 void WriteRef::dump() const {
    101   dbgs() << "IID=" << getSourceIndex() << ' ';
    102   if (isValid())
    103     getWriteState()->dump();
    104   else
    105     dbgs() << "(null)";
    106 }
    107 #endif
    108 
    109 void Instruction::dispatch(unsigned RCUToken) {
    110   assert(Stage == IS_INVALID);
    111   Stage = IS_AVAILABLE;
    112   RCUTokenID = RCUToken;
    113 
    114   // Check if input operands are already available.
    115   update();
    116 }
    117 
    118 void Instruction::execute() {
    119   assert(Stage == IS_READY);
    120   Stage = IS_EXECUTING;
    121 
    122   // Set the cycles left before the write-back stage.
    123   CyclesLeft = Desc.MaxLatency;
    124 
    125   for (UniqueDef &Def : Defs)
    126     Def->onInstructionIssued();
    127 
    128   // Transition to the "executed" stage if this is a zero-latency instruction.
    129   if (!CyclesLeft)
    130     Stage = IS_EXECUTED;
    131 }
    132 
    133 void Instruction::update() {
    134   assert(isDispatched() && "Unexpected instruction stage found!");
    135 
    136   if (!llvm::all_of(Uses, [](const UniqueUse &Use) { return Use->isReady(); }))
    137     return;
    138 
    139   // A partial register write cannot complete before a dependent write.
    140   auto IsDefReady = [&](const UniqueDef &Def) {
    141     if (const WriteState *Write = Def->getDependentWrite()) {
    142       int WriteLatency = Write->getCyclesLeft();
    143       if (WriteLatency == UNKNOWN_CYCLES)
    144         return false;
    145       return static_cast<unsigned>(WriteLatency) < Desc.MaxLatency;
    146     }
    147     return true;
    148   };
    149 
    150   if (llvm::all_of(Defs, IsDefReady))
    151     Stage = IS_READY;
    152 }
    153 
    154 void Instruction::cycleEvent() {
    155   if (isReady())
    156     return;
    157 
    158   if (isDispatched()) {
    159     for (UniqueUse &Use : Uses)
    160       Use->cycleEvent();
    161 
    162     update();
    163     return;
    164   }
    165 
    166   assert(isExecuting() && "Instruction not in-flight?");
    167   assert(CyclesLeft && "Instruction already executed?");
    168   for (UniqueDef &Def : Defs)
    169     Def->cycleEvent();
    170   CyclesLeft--;
    171   if (!CyclesLeft)
    172     Stage = IS_EXECUTED;
    173 }
    174 
    175 const unsigned WriteRef::INVALID_IID = std::numeric_limits<unsigned>::max();
    176 
    177 } // namespace mca
    178