OSDN Git Service

[llvm-mca] Remove unused flag -verbose. NFC
[android-x86/external-llvm.git] / 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