contrib/llvm/include/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 Pipeline to model register reads,
  12 /// register writes and instructions.
  13 ///
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LLVM_MCA_INSTRUCTION_H
  17 #define LLVM_MCA_INSTRUCTION_H
  18
  19 #include "llvm/ADT/ArrayRef.h"
  20 #include "llvm/ADT/STLExtras.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/Support/MathExtras.h"
  23
  24 #ifndef NDEBUG
  25 #include "llvm/Support/raw_ostream.h"
  26 #endif
  27
  28 #include <memory>
  29
  30 namespace llvm {
  31
  32 namespace mca {
  33
  34 constexpr int UNKNOWN_CYCLES = -512;
  35
  36 /// A register write descriptor.
  37 struct WriteDescriptor {
  38   // Operand index. The index is negative for implicit writes only.
  39   // For implicit writes, the actual operand index is computed performing
  40   // a bitwise not of the OpIndex.
  41   int OpIndex;
  42   // Write latency. Number of cycles before write-back stage.
  43   unsigned Latency;
  44   // This field is set to a value different than zero only if this
  45   // is an implicit definition.
  46   unsigned RegisterID;
  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   bool isImplicitWrite() const { return OpIndex < 0; };
  62 };
  63
  64 /// A register read descriptor.
  65 struct ReadDescriptor {
  66   // A MCOperand index. This is used by the Dispatch logic to identify register
  67   // reads. Implicit reads have negative indices. The actual operand index of an
  68   // implicit read is the bitwise not of field OpIndex.
  69   int OpIndex;
  70   // The actual "UseIdx". This is used to query the ReadAdvance table. Explicit
  71   // uses always come first in the sequence of uses.
  72   unsigned UseIndex;
  73   // This field is only set if this is an implicit read.
  74   unsigned RegisterID;
  75   // Scheduling Class Index. It is used to query the scheduling model for the
  76   // MCSchedClassDesc object.
  77   unsigned SchedClassID;
  78
  79   bool isImplicitRead() const { return OpIndex < 0; };
  80 };
  81
  82 class ReadState;
  83
  84 /// Tracks uses of a register definition (e.g. register write).
  85 ///
  86 /// Each implicit/explicit register write is associated with an instance of
  87 /// this class. A WriteState object tracks the dependent users of a
  88 /// register write. It also tracks how many cycles are left before the write
  89 /// back stage.
  90 class WriteState {
  91   const WriteDescriptor *WD;
  92   // On instruction issue, this field is set equal to the write latency.
  93   // Before instruction issue, this field defaults to -512, a special
  94   // value that represents an "unknown" number of cycles.
  95   int CyclesLeft;
  96
  97   // Actual register defined by this write. This field is only used
  98   // to speedup queries on the register file.
  99   // For implicit writes, this field always matches the value of
 100   // field RegisterID from WD.
 101   unsigned RegisterID;
 102
 103   // Physical register file that serves register RegisterID.
 104   unsigned PRFID;
 105
 106   // True if this write implicitly clears the upper portion of RegisterID's
 107   // super-registers.
 108   bool ClearsSuperRegs;
 109
 110   // True if this write is from a dependency breaking zero-idiom instruction.
 111   bool WritesZero;
 112
 113   // True if this write has been eliminated at register renaming stage.
 114   // Example: a register move doesn't consume scheduler/pipleline resources if
 115   // it is eliminated at register renaming stage. It still consumes
 116   // decode bandwidth, and ROB entries.
 117   bool IsEliminated;
 118
 119   // This field is set if this is a partial register write, and it has a false
 120   // dependency on any previous write of the same register (or a portion of it).
 121   // DependentWrite must be able to complete before this write completes, so
 122   // that we don't break the WAW, and the two writes can be merged together.
 123   const WriteState *DependentWrite;
 124
 125   // A partial write that is in a false dependency with this write.
 126   WriteState *PartialWrite;
 127
 128   unsigned DependentWriteCyclesLeft;
 129
 130   // A list of dependent reads. Users is a set of dependent
 131   // reads. A dependent read is added to the set only if CyclesLeft
 132   // is "unknown". As soon as CyclesLeft is 'known', each user in the set
 133   // gets notified with the actual CyclesLeft.
 134
 135   // The 'second' element of a pair is a "ReadAdvance" number of cycles.
 136   SmallVector<std::pair<ReadState *, int>, 4> Users;
 137
 138 public:
 139   WriteState(const WriteDescriptor &Desc, unsigned RegID,
 140              bool clearsSuperRegs = false, bool writesZero = false)
 141       : WD(&Desc), CyclesLeft(UNKNOWN_CYCLES), RegisterID(RegID), PRFID(0),
 142         ClearsSuperRegs(clearsSuperRegs), WritesZero(writesZero),
 143         IsEliminated(false), DependentWrite(nullptr), PartialWrite(nullptr),
 144         DependentWriteCyclesLeft(0) {}
 145
 146   WriteState(const WriteState &Other) = default;
 147   WriteState &operator=(const WriteState &Other) = default;
 148
 149   int getCyclesLeft() const { return CyclesLeft; }
 150   unsigned getWriteResourceID() const { return WD->SClassOrWriteResourceID; }
 151   unsigned getRegisterID() const { return RegisterID; }
 152   unsigned getRegisterFileID() const { return PRFID; }
 153   unsigned getLatency() const { return WD->Latency; }
 154
 155   void addUser(ReadState *Use, int ReadAdvance);
 156   void addUser(WriteState *Use);
 157
 158   unsigned getDependentWriteCyclesLeft() const {
 159     return DependentWriteCyclesLeft;
 160   }
 161
 162   unsigned getNumUsers() const {
 163     unsigned NumUsers = Users.size();
 164     if (PartialWrite)
 165       ++NumUsers;
 166     return NumUsers;
 167   }
 168
 169   bool clearsSuperRegisters() const { return ClearsSuperRegs; }
 170   bool isWriteZero() const { return WritesZero; }
 171   bool isEliminated() const { return IsEliminated; }
 172   bool isExecuted() const {
 173     return CyclesLeft != UNKNOWN_CYCLES && CyclesLeft <= 0;
 174   }
 175
 176   const WriteState *getDependentWrite() const { return DependentWrite; }
 177   void setDependentWrite(WriteState *Other) { DependentWrite = Other; }
 178   void writeStartEvent(unsigned Cycles) {
 179     DependentWriteCyclesLeft = Cycles;
 180     DependentWrite = nullptr;
 181   }
 182
 183   void setWriteZero() { WritesZero = true; }
 184   void setEliminated() {
 185     assert(Users.empty() && "Write is in an inconsistent state.");
 186     CyclesLeft = 0;
 187     IsEliminated = true;
 188   }
 189
 190   void setPRF(unsigned PRF) { PRFID = PRF; }
 191
 192   // On every cycle, update CyclesLeft and notify dependent users.
 193   void cycleEvent();
 194   void onInstructionIssued();
 195
 196 #ifndef NDEBUG
 197   void dump() const;
 198 #endif
 199 };
 200
 201 /// Tracks register operand latency in cycles.
 202 ///
 203 /// A read may be dependent on more than one write. This occurs when some
 204 /// writes only partially update the register associated to this read.
 205 class ReadState {
 206   const ReadDescriptor *RD;
 207   // Physical register identified associated to this read.
 208   unsigned RegisterID;
 209   // Physical register file that serves register RegisterID.
 210   unsigned PRFID;
 211   // Number of writes that contribute to the definition of RegisterID.
 212   // In the absence of partial register updates, the number of DependentWrites
 213   // cannot be more than one.
 214   unsigned DependentWrites;
 215   // Number of cycles left before RegisterID can be read. This value depends on
 216   // the latency of all the dependent writes. It defaults to UNKNOWN_CYCLES.
 217   // It gets set to the value of field TotalCycles only when the 'CyclesLeft' of
 218   // every dependent write is known.
 219   int CyclesLeft;
 220   // This field is updated on every writeStartEvent(). When the number of
 221   // dependent writes (i.e. field DependentWrite) is zero, this value is
 222   // propagated to field CyclesLeft.
 223   unsigned TotalCycles;
 224   // This field is set to true only if there are no dependent writes, and
 225   // there are no `CyclesLeft' to wait.
 226   bool IsReady;
 227   // True if this is a read from a known zero register.
 228   bool IsZero;
 229   // True if this register read is from a dependency-breaking instruction.
 230   bool IndependentFromDef;
 231
 232 public:
 233   ReadState(const ReadDescriptor &Desc, unsigned RegID)
 234       : RD(&Desc), RegisterID(RegID), PRFID(0), DependentWrites(0),
 235         CyclesLeft(UNKNOWN_CYCLES), TotalCycles(0), IsReady(true),
 236         IsZero(false), IndependentFromDef(false) {}
 237
 238   const ReadDescriptor &getDescriptor() const { return *RD; }
 239   unsigned getSchedClass() const { return RD->SchedClassID; }
 240   unsigned getRegisterID() const { return RegisterID; }
 241   unsigned getRegisterFileID() const { return PRFID; }
 242
 243   bool isReady() const { return IsReady; }
 244   bool isImplicitRead() const { return RD->isImplicitRead(); }
 245
 246   bool isIndependentFromDef() const { return IndependentFromDef; }
 247   void setIndependentFromDef() { IndependentFromDef = true; }
 248
 249   void cycleEvent();
 250   void writeStartEvent(unsigned Cycles);
 251   void setDependentWrites(unsigned Writes) {
 252     DependentWrites = Writes;
 253     IsReady = !Writes;
 254   }
 255
 256   bool isReadZero() const { return IsZero; }
 257   void setReadZero() { IsZero = true; }
 258   void setPRF(unsigned ID) { PRFID = ID; }
 259 };
 260
 261 /// A sequence of cycles.
 262 ///
 263 /// This class can be used as a building block to construct ranges of cycles.
 264 class CycleSegment {
 265   unsigned Begin; // Inclusive.
 266   unsigned End;   // Exclusive.
 267   bool Reserved;  // Resources associated to this segment must be reserved.
 268
 269 public:
 270   CycleSegment(unsigned StartCycle, unsigned EndCycle, bool IsReserved = false)
 271       : Begin(StartCycle), End(EndCycle), Reserved(IsReserved) {}
 272
 273   bool contains(unsigned Cycle) const { return Cycle >= Begin && Cycle < End; }
 274   bool startsAfter(const CycleSegment &CS) const { return End <= CS.Begin; }
 275   bool endsBefore(const CycleSegment &CS) const { return Begin >= CS.End; }
 276   bool overlaps(const CycleSegment &CS) const {
 277     return !startsAfter(CS) && !endsBefore(CS);
 278   }
 279   bool isExecuting() const { return Begin == 0 && End != 0; }
 280   bool isExecuted() const { return End == 0; }
 281   bool operator<(const CycleSegment &Other) const {
 282     return Begin < Other.Begin;
 283   }
 284   CycleSegment &operator--(void) {
 285     if (Begin)
 286       Begin--;
 287     if (End)
 288       End--;
 289     return *this;
 290   }
 291
 292   bool isValid() const { return Begin <= End; }
 293   unsigned size() const { return End - Begin; };
 294   void subtract(unsigned Cycles) {
 295     assert(End >= Cycles);
 296     End -= Cycles;
 297   }
 298
 299   unsigned begin() const { return Begin; }
 300   unsigned end() const { return End; }
 301   void setEnd(unsigned NewEnd) { End = NewEnd; }
 302   bool isReserved() const { return Reserved; }
 303   void setReserved() { Reserved = true; }
 304 };
 305
 306 /// Helper used by class InstrDesc to describe how hardware resources
 307 /// are used.
 308 ///
 309 /// This class describes how many resource units of a specific resource kind
 310 /// (and how many cycles) are "used" by an instruction.
 311 struct ResourceUsage {
 312   CycleSegment CS;
 313   unsigned NumUnits;
 314   ResourceUsage(CycleSegment Cycles, unsigned Units = 1)
 315       : CS(Cycles), NumUnits(Units) {}
 316   unsigned size() const { return CS.size(); }
 317   bool isReserved() const { return CS.isReserved(); }
 318   void setReserved() { CS.setReserved(); }
 319 };
 320
 321 /// An instruction descriptor
 322 struct InstrDesc {
 323   SmallVector<WriteDescriptor, 4> Writes; // Implicit writes are at the end.
 324   SmallVector<ReadDescriptor, 4> Reads;   // Implicit reads are at the end.
 325
 326   // For every resource used by an instruction of this kind, this vector
 327   // reports the number of "consumed cycles".
 328   SmallVector<std::pair<uint64_t, ResourceUsage>, 4> Resources;
 329
 330   // A list of buffered resources consumed by this instruction.
 331   SmallVector<uint64_t, 4> Buffers;
 332
 333   unsigned MaxLatency;
 334   // Number of MicroOps for this instruction.
 335   unsigned NumMicroOps;
 336
 337   bool MayLoad;
 338   bool MayStore;
 339   bool HasSideEffects;
 340   bool BeginGroup;
 341   bool EndGroup;
 342
 343   // True if all buffered resources are in-order, and there is at least one
 344   // buffer which is a dispatch hazard (BufferSize = 0).
 345   bool MustIssueImmediately;
 346
 347   // A zero latency instruction doesn't consume any scheduler resources.
 348   bool isZeroLatency() const { return !MaxLatency && Resources.empty(); }
 349
 350   InstrDesc() = default;
 351   InstrDesc(const InstrDesc &Other) = delete;
 352   InstrDesc &operator=(const InstrDesc &Other) = delete;
 353 };
 354
 355 /// Base class for instructions consumed by the simulation pipeline.
 356 ///
 357 /// This class tracks data dependencies as well as generic properties
 358 /// of the instruction.
 359 class InstructionBase {
 360   const InstrDesc &Desc;
 361
 362   // This field is set for instructions that are candidates for move
 363   // elimination. For more information about move elimination, see the
 364   // definition of RegisterMappingTracker in RegisterFile.h
 365   bool IsOptimizableMove;
 366
 367   // Output dependencies.
 368   // One entry per each implicit and explicit register definition.
 369   SmallVector<WriteState, 4> Defs;
 370
 371   // Input dependencies.
 372   // One entry per each implicit and explicit register use.
 373   SmallVector<ReadState, 4> Uses;
 374
 375 public:
 376   InstructionBase(const InstrDesc &D) : Desc(D), IsOptimizableMove(false) {}
 377
 378   SmallVectorImpl<WriteState> &getDefs() { return Defs; }
 379   const ArrayRef<WriteState> getDefs() const { return Defs; }
 380   SmallVectorImpl<ReadState> &getUses() { return Uses; }
 381   const ArrayRef<ReadState> getUses() const { return Uses; }
 382   const InstrDesc &getDesc() const { return Desc; }
 383
 384   unsigned getLatency() const { return Desc.MaxLatency; }
 385
 386   bool hasDependentUsers() const {
 387     return any_of(Defs,
 388                   [](const WriteState &Def) { return Def.getNumUsers() > 0; });
 389   }
 390
 391   unsigned getNumUsers() const {
 392     unsigned NumUsers = 0;
 393     for (const WriteState &Def : Defs)
 394       NumUsers += Def.getNumUsers();
 395     return NumUsers;
 396   }
 397
 398   // Returns true if this instruction is a candidate for move elimination.
 399   bool isOptimizableMove() const { return IsOptimizableMove; }
 400   void setOptimizableMove() { IsOptimizableMove = true; }
 401 };
 402
 403 /// An instruction propagated through the simulated instruction pipeline.
 404 ///
 405 /// This class is used to monitor changes to the internal state of instructions
 406 /// that are sent to the various components of the simulated hardware pipeline.
 407 class Instruction : public InstructionBase {
 408   enum InstrStage {
 409     IS_INVALID,   // Instruction in an invalid state.
 410     IS_AVAILABLE, // Instruction dispatched but operands are not ready.
 411     IS_READY,     // Instruction dispatched and operands ready.
 412     IS_EXECUTING, // Instruction issued.
 413     IS_EXECUTED,  // Instruction executed. Values are written back.
 414     IS_RETIRED    // Instruction retired.
 415   };
 416
 417   // The current instruction stage.
 418   enum InstrStage Stage;
 419
 420   // This value defaults to the instruction latency. This instruction is
 421   // considered executed when field CyclesLeft goes to zero.
 422   int CyclesLeft;
 423
 424   // Retire Unit token ID for this instruction.
 425   unsigned RCUTokenID;
 426
 427 public:
 428   Instruction(const InstrDesc &D)
 429       : InstructionBase(D), Stage(IS_INVALID), CyclesLeft(UNKNOWN_CYCLES),
 430         RCUTokenID(0) {}
 431
 432   unsigned getRCUTokenID() const { return RCUTokenID; }
 433   int getCyclesLeft() const { return CyclesLeft; }
 434
 435   // Transition to the dispatch stage, and assign a RCUToken to this
 436   // instruction. The RCUToken is used to track the completion of every
 437   // register write performed by this instruction.
 438   void dispatch(unsigned RCUTokenID);
 439
 440   // Instruction issued. Transition to the IS_EXECUTING state, and update
 441   // all the definitions.
 442   void execute();
 443
 444   // Force a transition from the IS_AVAILABLE state to the IS_READY state if
 445   // input operands are all ready. State transitions normally occur at the
 446   // beginning of a new cycle (see method cycleEvent()). However, the scheduler
 447   // may decide to promote instructions from the wait queue to the ready queue
 448   // as the result of another issue event.  This method is called every time the
 449   // instruction might have changed in state.
 450   void update();
 451
 452   bool isDispatched() const { return Stage == IS_AVAILABLE; }
 453   bool isReady() const { return Stage == IS_READY; }
 454   bool isExecuting() const { return Stage == IS_EXECUTING; }
 455   bool isExecuted() const { return Stage == IS_EXECUTED; }
 456   bool isRetired() const { return Stage == IS_RETIRED; }
 457
 458   bool isEliminated() const {
 459     return isReady() && getDefs().size() &&
 460            all_of(getDefs(),
 461                   [](const WriteState &W) { return W.isEliminated(); });
 462   }
 463
 464   // Forces a transition from state IS_AVAILABLE to state IS_EXECUTED.
 465   void forceExecuted();
 466
 467   void retire() {
 468     assert(isExecuted() && "Instruction is in an invalid state!");
 469     Stage = IS_RETIRED;
 470   }
 471
 472   void cycleEvent();
 473 };
 474
 475 /// An InstRef contains both a SourceMgr index and Instruction pair.  The index
 476 /// is used as a unique identifier for the instruction.  MCA will make use of
 477 /// this index as a key throughout MCA.
 478 class InstRef {
 479   std::pair<unsigned, Instruction *> Data;
 480
 481 public:
 482   InstRef() : Data(std::make_pair(0, nullptr)) {}
 483   InstRef(unsigned Index, Instruction *I) : Data(std::make_pair(Index, I)) {}
 484
 485   bool operator==(const InstRef &Other) const { return Data == Other.Data; }
 486
 487   unsigned getSourceIndex() const { return Data.first; }
 488   Instruction *getInstruction() { return Data.second; }
 489   const Instruction *getInstruction() const { return Data.second; }
 490
 491   /// Returns true if this references a valid instruction.
 492   operator bool() const { return Data.second != nullptr; }
 493
 494   /// Invalidate this reference.
 495   void invalidate() { Data.second = nullptr; }
 496
 497 #ifndef NDEBUG
 498   void print(raw_ostream &OS) const { OS << getSourceIndex(); }
 499 #endif
 500 };
 501
 502 #ifndef NDEBUG
 503 inline raw_ostream &operator<<(raw_ostream &OS, const InstRef &IR) {
 504   IR.print(OS);
 505   return OS;
 506 }
 507 #endif
 508
 509 /// A reference to a register write.
 510 ///
 511 /// This class is mainly used by the register file to describe register
 512 /// mappings. It correlates a register write to the source index of the
 513 /// defining instruction.
 514 class WriteRef {
 515   std::pair<unsigned, WriteState *> Data;
 516   static const unsigned INVALID_IID;
 517
 518 public:
 519   WriteRef() : Data(INVALID_IID, nullptr) {}
 520   WriteRef(unsigned SourceIndex, WriteState *WS) : Data(SourceIndex, WS) {}
 521
 522   unsigned getSourceIndex() const { return Data.first; }
 523   const WriteState *getWriteState() const { return Data.second; }
 524   WriteState *getWriteState() { return Data.second; }
 525   void invalidate() { Data.second = nullptr; }
 526   bool isWriteZero() const {
 527     assert(isValid() && "Invalid null WriteState found!");
 528     return getWriteState()->isWriteZero();
 529   }
 530
 531   /// Returns true if this register write has been executed, and the new
 532   /// register value is therefore available to users.
 533   bool isAvailable() const {
 534     if (getSourceIndex() == INVALID_IID)
 535       return false;
 536     const WriteState *WS = getWriteState();
 537     return !WS || WS->isExecuted();
 538   }
 539
 540   bool isValid() const { return Data.first != INVALID_IID && Data.second; }
 541   bool operator==(const WriteRef &Other) const { return Data == Other.Data; }
 542
 543 #ifndef NDEBUG
 544   void dump() const;
 545 #endif
 546 };
 547
 548 } // namespace mca
 549 } // namespace llvm
 550
 551 #endif // LLVM_MCA_INSTRUCTION_H