tools/llvm-mca/Instruction.h

   1 //===--------------------- Instruction.h ------------------------*- 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 /// \file
  10 ///
  11 /// This file defines abstractions used by the Backend to model register reads,
  12 /// register writes and instructions.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_TOOLS_LLVM_MCA_INSTRUCTION_H
  17 #define LLVM_TOOLS_LLVM_MCA_INSTRUCTION_H
  18
  19 #include "llvm/Support/MathExtras.h"
  20 #include <memory>
  21 #include <set>
  22 #include <vector>
  23
  24 namespace mca {
  25
  26 struct WriteDescriptor;
  27 struct ReadDescriptor;
  28 class WriteState;
  29 class ReadState;
  30
  31 constexpr int UNKNOWN_CYCLES = -512;
  32
  33 /// \brief A register write descriptor.
  34 struct WriteDescriptor {
  35   // Operand index. -1 if this is an implicit write.
  36   int OpIndex;
  37   // Write latency. Number of cycles before write-back stage.
  38   int Latency;
  39   // This field is set to a value different than zero only if this
  40   // is an implicit definition.
  41   unsigned RegisterID;
  42   // True if this write generates a partial update of a super-registers.
  43   // On X86, this flag is set by byte/word writes on GPR registers. Also,
  44   // a write of an XMM register only partially updates the corresponding
  45   // YMM super-register if the write is associated to a legacy SSE instruction.
  46   bool FullyUpdatesSuperRegs;
  47   // Instruction itineraries would set this field to the SchedClass ID.
  48   // Otherwise, it defaults to the WriteResourceID from the MCWriteLatencyEntry
  49   // element associated to this write.
  50   // When computing read latencies, this value is matched against the
  51   // "ReadAdvance" information. The hardware backend may implement
  52   // dedicated forwarding paths to quickly propagate write results to dependent
  53   // instructions waiting in the reservation station (effectively bypassing the
  54   // write-back stage).
  55   unsigned SClassOrWriteResourceID;
  56   // True only if this is a write obtained from an optional definition.
  57   // Optional definitions are allowed to reference regID zero (i.e. "no
  58   // register").
  59   bool IsOptionalDef;
  60 };
  61
  62 /// \brief A register read descriptor.
  63 struct ReadDescriptor {
  64   // A MCOperand index. This is used by the Dispatch logic to identify register
  65   // reads. This field defaults to -1 if this is an implicit read.
  66   int OpIndex;
  67   // The actual "UseIdx". This is used to query the ReadAdvance table. Explicit
  68   // uses always come first in the sequence of uses.
  69   unsigned UseIndex;
  70   // This field is only set if this is an implicit read.
  71   unsigned RegisterID;
  72   // Scheduling Class Index. It is used to query the scheduling model for the
  73   // MCSchedClassDesc object.
  74   unsigned SchedClassID;
  75   // True if there may be a local forwarding logic in hardware to serve a
  76   // write used by this read. This information, along with SchedClassID, is
  77   // used to dynamically check at Instruction creation time, if the input
  78   // operands can benefit from a ReadAdvance bonus.
  79   bool HasReadAdvanceEntries;
  80 };
  81
  82 /// \brief Tracks uses of a register definition (e.g. register write).
  83 ///
  84 /// Each implicit/explicit register write is associated with an instance of
  85 /// this class. A WriteState object tracks the dependent users of a
  86 /// register write. It also tracks how many cycles are left before the write
  87 /// back stage.
  88 class WriteState {
  89   const WriteDescriptor &WD;
  90   // On instruction issue, this field is set equal to the write latency.
  91   // Before instruction issue, this field defaults to -512, a special
  92   // value that represents an "unknown" number of cycles.
  93   int CyclesLeft;
  94
  95   // Actual register defined by this write. This field is only used
  96   // to speedup queries on the register file.
  97   // For implicit writes, this field always matches the value of
  98   // field RegisterID from WD.
  99   unsigned RegisterID;
 100
 101   // A list of dependent reads. Users is a set of dependent
 102   // reads. A dependent read is added to the set only if CyclesLeft
 103   // is "unknown". As soon as CyclesLeft is 'known', each user in the set
 104   // gets notified with the actual CyclesLeft.
 105
 106   // The 'second' element of a pair is a "ReadAdvance" number of cycles.
 107   std::set<std::pair<ReadState *, int>> Users;
 108
 109 public:
 110   WriteState(const WriteDescriptor &Desc, unsigned RegID)
 111       : WD(Desc), CyclesLeft(UNKNOWN_CYCLES), RegisterID(RegID) {}
 112   WriteState(const WriteState &Other) = delete;
 113   WriteState &operator=(const WriteState &Other) = delete;
 114
 115   int getCyclesLeft() const { return CyclesLeft; }
 116   unsigned getWriteResourceID() const { return WD.SClassOrWriteResourceID; }
 117   unsigned getRegisterID() const { return RegisterID; }
 118
 119   void addUser(ReadState *Use, int ReadAdvance);
 120   bool fullyUpdatesSuperRegs() const { return WD.FullyUpdatesSuperRegs; }
 121
 122   // On every cycle, update CyclesLeft and notify dependent users.
 123   void cycleEvent();
 124   void onInstructionIssued();
 125
 126 #ifndef NDEBUG
 127   void dump() const;
 128 #endif
 129 };
 130
 131 /// \brief Tracks register operand latency in cycles.
 132 ///
 133 /// A read may be dependent on more than one write. This occurs when some
 134 /// writes only partially update the register associated to this read.
 135 class ReadState {
 136   const ReadDescriptor &RD;
 137   unsigned RegisterID;
 138   unsigned DependentWrites;
 139   int CyclesLeft;
 140   unsigned TotalCycles;
 141
 142 public:
 143   bool isReady() const {
 144     if (DependentWrites)
 145       return false;
 146     return (CyclesLeft == UNKNOWN_CYCLES || CyclesLeft == 0);
 147   }
 148
 149   ReadState(const ReadDescriptor &Desc, unsigned RegID)
 150       : RD(Desc), RegisterID(RegID), DependentWrites(0),
 151         CyclesLeft(UNKNOWN_CYCLES), TotalCycles(0) {}
 152   ReadState(const ReadState &Other) = delete;
 153   ReadState &operator=(const ReadState &Other) = delete;
 154
 155   const ReadDescriptor &getDescriptor() const { return RD; }
 156   unsigned getSchedClass() const { return RD.SchedClassID; }
 157   unsigned getRegisterID() const { return RegisterID; }
 158   void cycleEvent();
 159   void writeStartEvent(unsigned Cycles);
 160   void setDependentWrites(unsigned Writes) { DependentWrites = Writes; }
 161 };
 162
 163 /// \brief A sequence of cycles.
 164 ///
 165 /// This class can be used as a building block to construct ranges of cycles.
 166 class CycleSegment {
 167   unsigned Begin; // Inclusive.
 168   unsigned End;   // Exclusive.
 169   bool Reserved;  // Resources associated to this segment must be reserved.
 170
 171 public:
 172   CycleSegment(unsigned StartCycle, unsigned EndCycle, bool IsReserved = false)
 173       : Begin(StartCycle), End(EndCycle), Reserved(IsReserved) {}
 174
 175   bool contains(unsigned Cycle) const { return Cycle >= Begin && Cycle < End; }
 176   bool startsAfter(const CycleSegment &CS) const { return End <= CS.Begin; }
 177   bool endsBefore(const CycleSegment &CS) const { return Begin >= CS.End; }
 178   bool overlaps(const CycleSegment &CS) const {
 179     return !startsAfter(CS) && !endsBefore(CS);
 180   }
 181   bool isExecuting() const { return Begin == 0 && End != 0; }
 182   bool isExecuted() const { return End == 0; }
 183   bool operator<(const CycleSegment &Other) const {
 184     return Begin < Other.Begin;
 185   }
 186   CycleSegment &operator--(void) {
 187     if (Begin)
 188       Begin--;
 189     if (End)
 190       End--;
 191     return *this;
 192   }
 193
 194   bool isValid() const { return Begin <= End; }
 195   unsigned size() const { return End - Begin; };
 196   void Subtract(unsigned Cycles) {
 197     assert(End >= Cycles);
 198     End -= Cycles;
 199   }
 200
 201   unsigned begin() const { return Begin; }
 202   unsigned end() const { return End; }
 203   void setEnd(unsigned NewEnd) { End = NewEnd; }
 204   bool isReserved() const { return Reserved; }
 205   void setReserved() { Reserved = true; }
 206 };
 207
 208 /// \brief Helper used by class InstrDesc to describe how hardware resources
 209 /// are used.
 210 ///
 211 /// This class describes how many resource units of a specific resource kind
 212 /// (and how many cycles) are "used" by an instruction.
 213 struct ResourceUsage {
 214   CycleSegment CS;
 215   unsigned NumUnits;
 216   ResourceUsage(CycleSegment Cycles, unsigned Units = 1)
 217       : CS(Cycles), NumUnits(Units) {}
 218   unsigned size() const { return CS.size(); }
 219   bool isReserved() const { return CS.isReserved(); }
 220   void setReserved() { CS.setReserved(); }
 221 };
 222
 223 /// \brief An instruction descriptor
 224 struct InstrDesc {
 225   std::vector<WriteDescriptor> Writes; // Implicit writes are at the end.
 226   std::vector<ReadDescriptor> Reads;   // Implicit reads are at the end.
 227
 228   // For every resource used by an instruction of this kind, this vector
 229   // reports the number of "consumed cycles".
 230   std::vector<std::pair<uint64_t, ResourceUsage>> Resources;
 231
 232   // A list of buffered resources consumed by this instruction.
 233   std::vector<uint64_t> Buffers;
 234   unsigned MaxLatency;
 235   // Number of MicroOps for this instruction.
 236   unsigned NumMicroOps;
 237
 238   bool MayLoad;
 239   bool MayStore;
 240   bool HasSideEffects;
 241 };
 242
 243 /// An instruction dispatched to the out-of-order backend.
 244 ///
 245 /// This class is used to monitor changes in the internal state of instructions
 246 /// that are dispatched by the DispatchUnit to the hardware schedulers.
 247 class Instruction {
 248   const InstrDesc &Desc;
 249
 250   enum InstrStage {
 251     IS_INVALID,   // Instruction in an invalid state.
 252     IS_AVAILABLE, // Instruction dispatched but operands are not ready.
 253     IS_READY,     // Instruction dispatched and operands ready.
 254     IS_EXECUTING, // Instruction issued.
 255     IS_EXECUTED,  // Instruction executed. Values are written back.
 256     IS_RETIRED    // Instruction retired.
 257   };
 258
 259   // The current instruction stage.
 260   enum InstrStage Stage;
 261
 262   // This value defaults to the instruction latency. This instruction is
 263   // considered executed when field CyclesLeft goes to zero.
 264   int CyclesLeft;
 265
 266   // Retire Unit token ID for this instruction.
 267   unsigned RCUTokenID;
 268
 269   using UniqueDef = std::unique_ptr<WriteState>;
 270   using UniqueUse = std::unique_ptr<ReadState>;
 271   using VecDefs = std::vector<UniqueDef>;
 272   using VecUses = std::vector<UniqueUse>;
 273
 274   // Output dependencies.
 275   // One entry per each implicit and explicit register definition.
 276   VecDefs Defs;
 277
 278   // Input dependencies.
 279   // One entry per each implicit and explicit register use.
 280   VecUses Uses;
 281
 282 public:
 283   Instruction(const InstrDesc &D)
 284       : Desc(D), Stage(IS_INVALID), CyclesLeft(-1) {}
 285   Instruction(const Instruction &Other) = delete;
 286   Instruction &operator=(const Instruction &Other) = delete;
 287
 288   VecDefs &getDefs() { return Defs; }
 289   const VecDefs &getDefs() const { return Defs; }
 290   VecUses &getUses() { return Uses; }
 291   const VecUses &getUses() const { return Uses; }
 292   const InstrDesc &getDesc() const { return Desc; }
 293   unsigned getRCUTokenID() const { return RCUTokenID; }
 294
 295   // Transition to the dispatch stage, and assign a RCUToken to this
 296   // instruction. The RCUToken is used to track the completion of every
 297   // register write performed by this instruction.
 298   void dispatch(unsigned RCUTokenID);
 299
 300   // Instruction issued. Transition to the IS_EXECUTING state, and update
 301   // all the definitions.
 302   void execute();
 303
 304   // Force a transition from the IS_AVAILABLE state to the IS_READY state if
 305   // input operands are all ready. State transitions normally occur at the
 306   // beginning of a new cycle (see method cycleEvent()). However, the scheduler
 307   // may decide to promote instructions from the wait queue to the ready queue
 308   // as the result of another issue event.  This method is called every time the
 309   // instruction might have changed in state.
 310   void update();
 311
 312   bool isDispatched() const { return Stage == IS_AVAILABLE; }
 313   bool isReady() const { return Stage == IS_READY; }
 314   bool isExecuting() const { return Stage == IS_EXECUTING; }
 315   bool isExecuted() const { return Stage == IS_EXECUTED; }
 316   bool isZeroLatency() const;
 317
 318   void retire() {
 319     assert(isExecuted() && "Instruction is in an invalid state!");
 320     Stage = IS_RETIRED;
 321   }
 322
 323   void cycleEvent();
 324 };
 325 } // namespace mca
 326
 327 #endif