1 //===--------------------- Instruction.h ------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 /// This file defines abstractions used by the Pipeline to model register reads,
12 /// register writes and instructions.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_TOOLS_LLVM_MCA_INSTRUCTION_H
17 #define LLVM_TOOLS_LLVM_MCA_INSTRUCTION_H
19 #include "llvm/Support/MathExtras.h"
22 #include "llvm/Support/raw_ostream.h"
31 constexpr int UNKNOWN_CYCLES = -512;
33 /// A register write descriptor.
34 struct WriteDescriptor {
35 // Operand index. The index is negative for implicit writes only.
36 // For implicit writes, the actual operand index is computed performing
37 // a bitwise not of the OpIndex.
39 // Write latency. Number of cycles before write-back stage.
41 // This field is set to a value different than zero only if this
42 // is an implicit definition.
44 // Instruction itineraries would set this field to the SchedClass ID.
45 // Otherwise, it defaults to the WriteResourceID from the MCWriteLatencyEntry
46 // element associated to this write.
47 // When computing read latencies, this value is matched against the
48 // "ReadAdvance" information. The hardware backend may implement
49 // dedicated forwarding paths to quickly propagate write results to dependent
50 // instructions waiting in the reservation station (effectively bypassing the
52 unsigned SClassOrWriteResourceID;
53 // True only if this is a write obtained from an optional definition.
54 // Optional definitions are allowed to reference regID zero (i.e. "no
58 bool isImplicitWrite() const { return OpIndex < 0; };
61 /// A register read descriptor.
62 struct ReadDescriptor {
63 // A MCOperand index. This is used by the Dispatch logic to identify register
64 // reads. Implicit reads have negative indices. The actual operand index of an
65 // implicit read is the bitwise not of field OpIndex.
67 // The actual "UseIdx". This is used to query the ReadAdvance table. Explicit
68 // uses always come first in the sequence of uses.
70 // This field is only set if this is an implicit read.
72 // Scheduling Class Index. It is used to query the scheduling model for the
73 // MCSchedClassDesc object.
74 unsigned SchedClassID;
76 bool isImplicitRead() const { return OpIndex < 0; };
81 /// Tracks uses of a register definition (e.g. register write).
83 /// Each implicit/explicit register write is associated with an instance of
84 /// this class. A WriteState object tracks the dependent users of a
85 /// register write. It also tracks how many cycles are left before the write
88 const WriteDescriptor &WD;
89 // On instruction issue, this field is set equal to the write latency.
90 // Before instruction issue, this field defaults to -512, a special
91 // value that represents an "unknown" number of cycles.
94 // Actual register defined by this write. This field is only used
95 // to speedup queries on the register file.
96 // For implicit writes, this field always matches the value of
97 // field RegisterID from WD.
100 // True if this write implicitly clears the upper portion of RegisterID's
102 bool ClearsSuperRegs;
104 // This field is set if this is a partial register write, and it has a false
105 // dependency on any previous write of the same register (or a portion of it).
106 // DependentWrite must be able to complete before this write completes, so
107 // that we don't break the WAW, and the two writes can be merged together.
108 const WriteState *DependentWrite;
110 // A list of dependent reads. Users is a set of dependent
111 // reads. A dependent read is added to the set only if CyclesLeft
112 // is "unknown". As soon as CyclesLeft is 'known', each user in the set
113 // gets notified with the actual CyclesLeft.
115 // The 'second' element of a pair is a "ReadAdvance" number of cycles.
116 std::set<std::pair<ReadState *, int>> Users;
119 WriteState(const WriteDescriptor &Desc, unsigned RegID,
120 bool clearsSuperRegs = false)
121 : WD(Desc), CyclesLeft(UNKNOWN_CYCLES), RegisterID(RegID),
122 ClearsSuperRegs(clearsSuperRegs), DependentWrite(nullptr) {}
123 WriteState(const WriteState &Other) = delete;
124 WriteState &operator=(const WriteState &Other) = delete;
126 int getCyclesLeft() const { return CyclesLeft; }
127 unsigned getWriteResourceID() const { return WD.SClassOrWriteResourceID; }
128 unsigned getRegisterID() const { return RegisterID; }
129 unsigned getLatency() const { return WD.Latency; }
131 void addUser(ReadState *Use, int ReadAdvance);
132 unsigned getNumUsers() const { return Users.size(); }
133 bool clearsSuperRegisters() const { return ClearsSuperRegs; }
135 const WriteState *getDependentWrite() const { return DependentWrite; }
136 void setDependentWrite(const WriteState *Write) { DependentWrite = Write; }
138 // On every cycle, update CyclesLeft and notify dependent users.
140 void onInstructionIssued();
147 /// Tracks register operand latency in cycles.
149 /// A read may be dependent on more than one write. This occurs when some
150 /// writes only partially update the register associated to this read.
152 const ReadDescriptor &RD;
153 // Physical register identified associated to this read.
155 // Number of writes that contribute to the definition of RegisterID.
156 // In the absence of partial register updates, the number of DependentWrites
157 // cannot be more than one.
158 unsigned DependentWrites;
159 // Number of cycles left before RegisterID can be read. This value depends on
160 // the latency of all the dependent writes. It defaults to UNKNOWN_CYCLES.
161 // It gets set to the value of field TotalCycles only when the 'CyclesLeft' of
162 // every dependent write is known.
164 // This field is updated on every writeStartEvent(). When the number of
165 // dependent writes (i.e. field DependentWrite) is zero, this value is
166 // propagated to field CyclesLeft.
167 unsigned TotalCycles;
168 // This field is set to true only if there are no dependent writes, and
169 // there are no `CyclesLeft' to wait.
173 ReadState(const ReadDescriptor &Desc, unsigned RegID)
174 : RD(Desc), RegisterID(RegID), DependentWrites(0),
175 CyclesLeft(UNKNOWN_CYCLES), TotalCycles(0), IsReady(true) {}
176 ReadState(const ReadState &Other) = delete;
177 ReadState &operator=(const ReadState &Other) = delete;
179 const ReadDescriptor &getDescriptor() const { return RD; }
180 unsigned getSchedClass() const { return RD.SchedClassID; }
181 unsigned getRegisterID() const { return RegisterID; }
183 bool isReady() const { return IsReady; }
184 bool isImplicitRead() const { return RD.isImplicitRead(); }
187 void writeStartEvent(unsigned Cycles);
188 void setDependentWrites(unsigned Writes) {
189 DependentWrites = Writes;
194 /// A sequence of cycles.
196 /// This class can be used as a building block to construct ranges of cycles.
198 unsigned Begin; // Inclusive.
199 unsigned End; // Exclusive.
200 bool Reserved; // Resources associated to this segment must be reserved.
203 CycleSegment(unsigned StartCycle, unsigned EndCycle, bool IsReserved = false)
204 : Begin(StartCycle), End(EndCycle), Reserved(IsReserved) {}
206 bool contains(unsigned Cycle) const { return Cycle >= Begin && Cycle < End; }
207 bool startsAfter(const CycleSegment &CS) const { return End <= CS.Begin; }
208 bool endsBefore(const CycleSegment &CS) const { return Begin >= CS.End; }
209 bool overlaps(const CycleSegment &CS) const {
210 return !startsAfter(CS) && !endsBefore(CS);
212 bool isExecuting() const { return Begin == 0 && End != 0; }
213 bool isExecuted() const { return End == 0; }
214 bool operator<(const CycleSegment &Other) const {
215 return Begin < Other.Begin;
217 CycleSegment &operator--(void) {
225 bool isValid() const { return Begin <= End; }
226 unsigned size() const { return End - Begin; };
227 void Subtract(unsigned Cycles) {
228 assert(End >= Cycles);
232 unsigned begin() const { return Begin; }
233 unsigned end() const { return End; }
234 void setEnd(unsigned NewEnd) { End = NewEnd; }
235 bool isReserved() const { return Reserved; }
236 void setReserved() { Reserved = true; }
239 /// Helper used by class InstrDesc to describe how hardware resources
242 /// This class describes how many resource units of a specific resource kind
243 /// (and how many cycles) are "used" by an instruction.
244 struct ResourceUsage {
247 ResourceUsage(CycleSegment Cycles, unsigned Units = 1)
248 : CS(Cycles), NumUnits(Units) {}
249 unsigned size() const { return CS.size(); }
250 bool isReserved() const { return CS.isReserved(); }
251 void setReserved() { CS.setReserved(); }
254 /// An instruction descriptor
256 std::vector<WriteDescriptor> Writes; // Implicit writes are at the end.
257 std::vector<ReadDescriptor> Reads; // Implicit reads are at the end.
259 // For every resource used by an instruction of this kind, this vector
260 // reports the number of "consumed cycles".
261 std::vector<std::pair<uint64_t, ResourceUsage>> Resources;
263 // A list of buffered resources consumed by this instruction.
264 std::vector<uint64_t> Buffers;
266 // Number of MicroOps for this instruction.
267 unsigned NumMicroOps;
273 // A zero latency instruction doesn't consume any scheduler resources.
274 bool isZeroLatency() const { return !MaxLatency && Resources.empty(); }
277 /// An instruction propagated through the simulated instruction pipeline.
279 /// This class is used to monitor changes to the internal state of instructions
280 /// that are sent to the various components of the simulated hardware pipeline.
282 const InstrDesc &Desc;
285 IS_INVALID, // Instruction in an invalid state.
286 IS_AVAILABLE, // Instruction dispatched but operands are not ready.
287 IS_READY, // Instruction dispatched and operands ready.
288 IS_EXECUTING, // Instruction issued.
289 IS_EXECUTED, // Instruction executed. Values are written back.
290 IS_RETIRED // Instruction retired.
293 // The current instruction stage.
294 enum InstrStage Stage;
296 // This value defaults to the instruction latency. This instruction is
297 // considered executed when field CyclesLeft goes to zero.
300 // Retire Unit token ID for this instruction.
305 using UniqueDef = std::unique_ptr<WriteState>;
306 using UniqueUse = std::unique_ptr<ReadState>;
307 using VecDefs = std::vector<UniqueDef>;
308 using VecUses = std::vector<UniqueUse>;
310 // Output dependencies.
311 // One entry per each implicit and explicit register definition.
314 // Input dependencies.
315 // One entry per each implicit and explicit register use.
319 Instruction(const InstrDesc &D)
320 : Desc(D), Stage(IS_INVALID), CyclesLeft(UNKNOWN_CYCLES), RCUTokenID(0),
321 IsDepBreaking(false) {}
322 Instruction(const Instruction &Other) = delete;
323 Instruction &operator=(const Instruction &Other) = delete;
325 VecDefs &getDefs() { return Defs; }
326 const VecDefs &getDefs() const { return Defs; }
327 VecUses &getUses() { return Uses; }
328 const VecUses &getUses() const { return Uses; }
329 const InstrDesc &getDesc() const { return Desc; }
330 unsigned getRCUTokenID() const { return RCUTokenID; }
331 int getCyclesLeft() const { return CyclesLeft; }
333 bool isDependencyBreaking() const { return IsDepBreaking; }
334 void setDependencyBreaking() { IsDepBreaking = true; }
336 unsigned getNumUsers() const {
337 unsigned NumUsers = 0;
338 for (const UniqueDef &Def : Defs)
339 NumUsers += Def->getNumUsers();
343 // Transition to the dispatch stage, and assign a RCUToken to this
344 // instruction. The RCUToken is used to track the completion of every
345 // register write performed by this instruction.
346 void dispatch(unsigned RCUTokenID);
348 // Instruction issued. Transition to the IS_EXECUTING state, and update
349 // all the definitions.
352 // Force a transition from the IS_AVAILABLE state to the IS_READY state if
353 // input operands are all ready. State transitions normally occur at the
354 // beginning of a new cycle (see method cycleEvent()). However, the scheduler
355 // may decide to promote instructions from the wait queue to the ready queue
356 // as the result of another issue event. This method is called every time the
357 // instruction might have changed in state.
360 bool isDispatched() const { return Stage == IS_AVAILABLE; }
361 bool isReady() const { return Stage == IS_READY; }
362 bool isExecuting() const { return Stage == IS_EXECUTING; }
363 bool isExecuted() const { return Stage == IS_EXECUTED; }
364 bool isRetired() const { return Stage == IS_RETIRED; }
367 assert(isExecuted() && "Instruction is in an invalid state!");
374 /// An InstRef contains both a SourceMgr index and Instruction pair. The index
375 /// is used as a unique identifier for the instruction. MCA will make use of
376 /// this index as a key throughout MCA.
377 class InstRef : public std::pair<unsigned, Instruction *> {
379 InstRef() : std::pair<unsigned, Instruction *>(0, nullptr) {}
380 InstRef(unsigned Index, Instruction *I)
381 : std::pair<unsigned, Instruction *>(Index, I) {}
383 unsigned getSourceIndex() const { return first; }
384 Instruction *getInstruction() { return second; }
385 const Instruction *getInstruction() const { return second; }
387 /// Returns true if this InstRef has been populated.
388 bool isValid() const { return second != nullptr; }
391 void print(llvm::raw_ostream &OS) const { OS << getSourceIndex(); }
396 inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const InstRef &IR) {
402 /// A reference to a register write.
404 /// This class is mainly used by the register file to describe register
405 /// mappings. It correlates a register write to the source index of the
406 /// defining instruction.
408 std::pair<unsigned, WriteState *> Data;
409 static const unsigned INVALID_IID;
412 WriteRef() : Data(INVALID_IID, nullptr) {}
413 WriteRef(unsigned SourceIndex, WriteState *WS) : Data(SourceIndex, WS) {}
415 unsigned getSourceIndex() const { return Data.first; }
416 const WriteState *getWriteState() const { return Data.second; }
417 WriteState *getWriteState() { return Data.second; }
418 void invalidate() { Data = std::make_pair(INVALID_IID, nullptr); }
420 bool isValid() const {
421 return Data.first != INVALID_IID && Data.second != nullptr;
423 bool operator==(const WriteRef &Other) const {
424 return Data == Other.Data;