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 552