• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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_TOOLS_LLVM_MCA_INSTRUCTION_H
17 #define LLVM_TOOLS_LLVM_MCA_INSTRUCTION_H
18 
19 #include "llvm/Support/MathExtras.h"
20 
21 #ifndef NDEBUG
22 #include "llvm/Support/raw_ostream.h"
23 #endif
24 
25 #include <memory>
26 #include <set>
27 #include <vector>
28 
29 namespace mca {
30 
31 constexpr int UNKNOWN_CYCLES = -512;
32 
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.
38   int OpIndex;
39   // Write latency. Number of cycles before write-back stage.
40   unsigned Latency;
41   // This field is set to a value different than zero only if this
42   // is an implicit definition.
43   unsigned RegisterID;
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
51   // write-back stage).
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
55   // register").
56   bool IsOptionalDef;
57 
isImplicitWriteWriteDescriptor58   bool isImplicitWrite() const { return OpIndex < 0; };
59 };
60 
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.
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 
isImplicitReadReadDescriptor76   bool isImplicitRead() const { return OpIndex < 0; };
77 };
78 
79 class ReadState;
80 
81 /// Tracks uses of a register definition (e.g. register write).
82 ///
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
86 /// back stage.
87 class WriteState {
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.
92   int CyclesLeft;
93 
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.
98   unsigned RegisterID;
99 
100   // True if this write implicitly clears the upper portion of RegisterID's
101   // super-registers.
102   bool ClearsSuperRegs;
103 
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;
109 
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.
114 
115   // The 'second' element of a pair is a "ReadAdvance" number of cycles.
116   std::set<std::pair<ReadState *, int>> Users;
117 
118 public:
119   WriteState(const WriteDescriptor &Desc, unsigned RegID,
120              bool clearsSuperRegs = false)
WD(Desc)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;
125 
getCyclesLeft()126   int getCyclesLeft() const { return CyclesLeft; }
getWriteResourceID()127   unsigned getWriteResourceID() const { return WD.SClassOrWriteResourceID; }
getRegisterID()128   unsigned getRegisterID() const { return RegisterID; }
getLatency()129   unsigned getLatency() const { return WD.Latency; }
130 
131   void addUser(ReadState *Use, int ReadAdvance);
getNumUsers()132   unsigned getNumUsers() const { return Users.size(); }
clearsSuperRegisters()133   bool clearsSuperRegisters() const { return ClearsSuperRegs; }
134 
getDependentWrite()135   const WriteState *getDependentWrite() const { return DependentWrite; }
setDependentWrite(const WriteState * Write)136   void setDependentWrite(const WriteState *Write) { DependentWrite = Write; }
137 
138   // On every cycle, update CyclesLeft and notify dependent users.
139   void cycleEvent();
140   void onInstructionIssued();
141 
142 #ifndef NDEBUG
143   void dump() const;
144 #endif
145 };
146 
147 /// Tracks register operand latency in cycles.
148 ///
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.
151 class ReadState {
152   const ReadDescriptor &RD;
153   // Physical register identified associated to this read.
154   unsigned RegisterID;
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.
163   int CyclesLeft;
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.
170   bool IsReady;
171 
172 public:
ReadState(const ReadDescriptor & Desc,unsigned RegID)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;
178 
getDescriptor()179   const ReadDescriptor &getDescriptor() const { return RD; }
getSchedClass()180   unsigned getSchedClass() const { return RD.SchedClassID; }
getRegisterID()181   unsigned getRegisterID() const { return RegisterID; }
182 
isReady()183   bool isReady() const { return IsReady; }
isImplicitRead()184   bool isImplicitRead() const { return RD.isImplicitRead(); }
185 
186   void cycleEvent();
187   void writeStartEvent(unsigned Cycles);
setDependentWrites(unsigned Writes)188   void setDependentWrites(unsigned Writes) {
189     DependentWrites = Writes;
190     IsReady = !Writes;
191   }
192 };
193 
194 /// A sequence of cycles.
195 ///
196 /// This class can be used as a building block to construct ranges of cycles.
197 class CycleSegment {
198   unsigned Begin; // Inclusive.
199   unsigned End;   // Exclusive.
200   bool Reserved;  // Resources associated to this segment must be reserved.
201 
202 public:
203   CycleSegment(unsigned StartCycle, unsigned EndCycle, bool IsReserved = false)
Begin(StartCycle)204       : Begin(StartCycle), End(EndCycle), Reserved(IsReserved) {}
205 
contains(unsigned Cycle)206   bool contains(unsigned Cycle) const { return Cycle >= Begin && Cycle < End; }
startsAfter(const CycleSegment & CS)207   bool startsAfter(const CycleSegment &CS) const { return End <= CS.Begin; }
endsBefore(const CycleSegment & CS)208   bool endsBefore(const CycleSegment &CS) const { return Begin >= CS.End; }
overlaps(const CycleSegment & CS)209   bool overlaps(const CycleSegment &CS) const {
210     return !startsAfter(CS) && !endsBefore(CS);
211   }
isExecuting()212   bool isExecuting() const { return Begin == 0 && End != 0; }
isExecuted()213   bool isExecuted() const { return End == 0; }
214   bool operator<(const CycleSegment &Other) const {
215     return Begin < Other.Begin;
216   }
217   CycleSegment &operator--(void) {
218     if (Begin)
219       Begin--;
220     if (End)
221       End--;
222     return *this;
223   }
224 
isValid()225   bool isValid() const { return Begin <= End; }
size()226   unsigned size() const { return End - Begin; };
Subtract(unsigned Cycles)227   void Subtract(unsigned Cycles) {
228     assert(End >= Cycles);
229     End -= Cycles;
230   }
231 
begin()232   unsigned begin() const { return Begin; }
end()233   unsigned end() const { return End; }
setEnd(unsigned NewEnd)234   void setEnd(unsigned NewEnd) { End = NewEnd; }
isReserved()235   bool isReserved() const { return Reserved; }
setReserved()236   void setReserved() { Reserved = true; }
237 };
238 
239 /// Helper used by class InstrDesc to describe how hardware resources
240 /// are used.
241 ///
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 {
245   CycleSegment CS;
246   unsigned NumUnits;
247   ResourceUsage(CycleSegment Cycles, unsigned Units = 1)
CSResourceUsage248       : CS(Cycles), NumUnits(Units) {}
sizeResourceUsage249   unsigned size() const { return CS.size(); }
isReservedResourceUsage250   bool isReserved() const { return CS.isReserved(); }
setReservedResourceUsage251   void setReserved() { CS.setReserved(); }
252 };
253 
254 /// An instruction descriptor
255 struct InstrDesc {
256   std::vector<WriteDescriptor> Writes; // Implicit writes are at the end.
257   std::vector<ReadDescriptor> Reads;   // Implicit reads are at the end.
258 
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;
262 
263   // A list of buffered resources consumed by this instruction.
264   std::vector<uint64_t> Buffers;
265   unsigned MaxLatency;
266   // Number of MicroOps for this instruction.
267   unsigned NumMicroOps;
268 
269   bool MayLoad;
270   bool MayStore;
271   bool HasSideEffects;
272 
273   // A zero latency instruction doesn't consume any scheduler resources.
isZeroLatencyInstrDesc274   bool isZeroLatency() const { return !MaxLatency && Resources.empty(); }
275 };
276 
277 /// An instruction propagated through the simulated instruction pipeline.
278 ///
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.
281 class Instruction {
282   const InstrDesc &Desc;
283 
284   enum InstrStage {
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.
291   };
292 
293   // The current instruction stage.
294   enum InstrStage Stage;
295 
296   // This value defaults to the instruction latency. This instruction is
297   // considered executed when field CyclesLeft goes to zero.
298   int CyclesLeft;
299 
300   // Retire Unit token ID for this instruction.
301   unsigned RCUTokenID;
302 
303   bool IsDepBreaking;
304 
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>;
309 
310   // Output dependencies.
311   // One entry per each implicit and explicit register definition.
312   VecDefs Defs;
313 
314   // Input dependencies.
315   // One entry per each implicit and explicit register use.
316   VecUses Uses;
317 
318 public:
Instruction(const InstrDesc & D)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;
324 
getDefs()325   VecDefs &getDefs() { return Defs; }
getDefs()326   const VecDefs &getDefs() const { return Defs; }
getUses()327   VecUses &getUses() { return Uses; }
getUses()328   const VecUses &getUses() const { return Uses; }
getDesc()329   const InstrDesc &getDesc() const { return Desc; }
getRCUTokenID()330   unsigned getRCUTokenID() const { return RCUTokenID; }
getCyclesLeft()331   int getCyclesLeft() const { return CyclesLeft; }
332 
isDependencyBreaking()333   bool isDependencyBreaking() const { return IsDepBreaking; }
setDependencyBreaking()334   void setDependencyBreaking() { IsDepBreaking = true; }
335 
getNumUsers()336   unsigned getNumUsers() const {
337     unsigned NumUsers = 0;
338     for (const UniqueDef &Def : Defs)
339       NumUsers += Def->getNumUsers();
340     return NumUsers;
341   }
342 
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);
347 
348   // Instruction issued. Transition to the IS_EXECUTING state, and update
349   // all the definitions.
350   void execute();
351 
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.
358   void update();
359 
isDispatched()360   bool isDispatched() const { return Stage == IS_AVAILABLE; }
isReady()361   bool isReady() const { return Stage == IS_READY; }
isExecuting()362   bool isExecuting() const { return Stage == IS_EXECUTING; }
isExecuted()363   bool isExecuted() const { return Stage == IS_EXECUTED; }
isRetired()364   bool isRetired() const { return Stage == IS_RETIRED; }
365 
retire()366   void retire() {
367     assert(isExecuted() && "Instruction is in an invalid state!");
368     Stage = IS_RETIRED;
369   }
370 
371   void cycleEvent();
372 };
373 
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 *> {
378 public:
InstRef()379   InstRef() : std::pair<unsigned, Instruction *>(0, nullptr) {}
InstRef(unsigned Index,Instruction * I)380   InstRef(unsigned Index, Instruction *I)
381       : std::pair<unsigned, Instruction *>(Index, I) {}
382 
getSourceIndex()383   unsigned getSourceIndex() const { return first; }
getInstruction()384   Instruction *getInstruction() { return second; }
getInstruction()385   const Instruction *getInstruction() const { return second; }
386 
387   /// Returns true if  this InstRef has been populated.
isValid()388   bool isValid() const { return second != nullptr; }
389 
390 #ifndef NDEBUG
print(llvm::raw_ostream & OS)391   void print(llvm::raw_ostream &OS) const { OS << getSourceIndex(); }
392 #endif
393 };
394 
395 #ifndef NDEBUG
396 inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const InstRef &IR) {
397   IR.print(OS);
398   return OS;
399 }
400 #endif
401 
402 /// A reference to a register write.
403 ///
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.
407 class WriteRef {
408   std::pair<unsigned, WriteState *> Data;
409   static const unsigned INVALID_IID;
410 
411 public:
WriteRef()412   WriteRef() : Data(INVALID_IID, nullptr) {}
WriteRef(unsigned SourceIndex,WriteState * WS)413   WriteRef(unsigned SourceIndex, WriteState *WS) : Data(SourceIndex, WS) {}
414 
getSourceIndex()415   unsigned getSourceIndex() const { return Data.first; }
getWriteState()416   const WriteState *getWriteState() const { return Data.second; }
getWriteState()417   WriteState *getWriteState() { return Data.second; }
invalidate()418   void invalidate() { Data = std::make_pair(INVALID_IID, nullptr); }
419 
isValid()420   bool isValid() const {
421     return Data.first != INVALID_IID && Data.second != nullptr;
422   }
423   bool operator==(const WriteRef &Other) const {
424     return Data == Other.Data;
425   }
426 
427 #ifndef NDEBUG
428   void dump() const;
429 #endif
430 };
431 
432 } // namespace mca
433 
434 #endif
435