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 Backend 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"
26 struct WriteDescriptor;
27 struct ReadDescriptor;
31 constexpr int UNKNOWN_CYCLES = -512;
33 /// \brief A register write descriptor.
34 struct WriteDescriptor {
35 // Operand index. -1 if this is an implicit write.
37 // Write latency. Number of cycles before write-back stage.
39 // This field is set to a value different than zero only if this
40 // is an implicit definition.
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
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
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.
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;
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;
82 /// \brief Tracks uses of a register definition (e.g. register write).
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
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.
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.
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.
106 // The 'second' element of a pair is a "ReadAdvance" number of cycles.
107 std::set<std::pair<ReadState *, int>> Users;
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;
115 int getCyclesLeft() const { return CyclesLeft; }
116 unsigned getWriteResourceID() const { return WD.SClassOrWriteResourceID; }
117 unsigned getRegisterID() const { return RegisterID; }
119 void addUser(ReadState *Use, int ReadAdvance);
120 bool fullyUpdatesSuperRegs() const { return WD.FullyUpdatesSuperRegs; }
122 // On every cycle, update CyclesLeft and notify dependent users.
124 void onInstructionIssued();
131 /// \brief Tracks register operand latency in cycles.
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.
136 const ReadDescriptor &RD;
138 unsigned DependentWrites;
140 unsigned TotalCycles;
143 bool isReady() const {
146 return (CyclesLeft == UNKNOWN_CYCLES || CyclesLeft == 0);
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;
155 const ReadDescriptor &getDescriptor() const { return RD; }
156 unsigned getSchedClass() const { return RD.SchedClassID; }
157 unsigned getRegisterID() const { return RegisterID; }
159 void writeStartEvent(unsigned Cycles);
160 void setDependentWrites(unsigned Writes) { DependentWrites = Writes; }
163 /// \brief A sequence of cycles.
165 /// This class can be used as a building block to construct ranges of cycles.
167 unsigned Begin; // Inclusive.
168 unsigned End; // Exclusive.
169 bool Reserved; // Resources associated to this segment must be reserved.
172 CycleSegment(unsigned StartCycle, unsigned EndCycle, bool IsReserved = false)
173 : Begin(StartCycle), End(EndCycle), Reserved(IsReserved) {}
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);
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;
186 CycleSegment &operator--(void) {
194 bool isValid() const { return Begin <= End; }
195 unsigned size() const { return End - Begin; };
196 void Subtract(unsigned Cycles) {
197 assert(End >= Cycles);
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; }
208 /// \brief Helper used by class InstrDesc to describe how hardware resources
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 {
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(); }
223 /// \brief An instruction descriptor
225 std::vector<WriteDescriptor> Writes; // Implicit writes are at the end.
226 std::vector<ReadDescriptor> Reads; // Implicit reads are at the end.
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;
232 // A list of buffered resources consumed by this instruction.
233 std::vector<uint64_t> Buffers;
235 // Number of MicroOps for this instruction.
236 unsigned NumMicroOps;
243 /// An instruction dispatched to the out-of-order backend.
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.
248 const InstrDesc &Desc;
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.
259 // The current instruction stage.
260 enum InstrStage Stage;
262 // This value defaults to the instruction latency. This instruction is
263 // considered executed when field CyclesLeft goes to zero.
266 // Retire Unit token ID for this instruction.
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>;
274 // Output dependencies.
275 // One entry per each implicit and explicit register definition.
278 // Input dependencies.
279 // One entry per each implicit and explicit register use.
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;
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; }
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);
300 // Instruction issued. Transition to the IS_EXECUTING state, and update
301 // all the definitions.
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.
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;
319 assert(isExecuted() && "Instruction is in an invalid state!");