| //===----------------------- Dispatch.h -------------------------*- C++ -*-===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| /// \file |
| /// |
| /// This file implements classes that are used to model register files, |
| /// reorder buffers and the hardware dispatch logic. |
| /// |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_TOOLS_LLVM_MCA_DISPATCH_H |
| #define LLVM_TOOLS_LLVM_MCA_DISPATCH_H |
| |
| #include "Instruction.h" |
| #include "llvm/MC/MCRegisterInfo.h" |
| #include "llvm/MC/MCSubtargetInfo.h" |
| #include <map> |
| |
| namespace mca { |
| |
| class WriteState; |
| class DispatchUnit; |
| class Scheduler; |
| class Backend; |
| |
| /// \brief Manages hardware register files, and tracks data dependencies |
| /// between registers. |
| class RegisterFile { |
| const llvm::MCRegisterInfo &MRI; |
| |
| // Each register file is described by an instance of RegisterMappingTracker. |
| // RegisterMappingTracker tracks the number of register mappings dynamically |
| // allocated during the execution. |
| struct RegisterMappingTracker { |
| // Total number of register mappings that are available for register |
| // renaming. A value of zero for this field means: this register file has |
| // an unbounded number of registers. |
| const unsigned TotalMappings; |
| // Number of mappings that are currently in use. |
| unsigned NumUsedMappings; |
| |
| RegisterMappingTracker(unsigned NumMappings) |
| : TotalMappings(NumMappings), NumUsedMappings(0) {} |
| }; |
| |
| // This is where information related to the various register files is kept. |
| // This set always contains at least one register file at index #0. That |
| // register file "sees" all the physical registers declared by the target, and |
| // (by default) it allows an unbound number of mappings. |
| // Users can limit the number of mappings that can be created by register file |
| // #0 through the command line flag `-register-file-size`. |
| llvm::SmallVector<RegisterMappingTracker, 4> RegisterFiles; |
| |
| // RegisterMapping objects are mainly used to track physical register |
| // definitions. A WriteState object describes a register definition, and it is |
| // used to track RAW dependencies (see Instruction.h). A RegisterMapping |
| // object also specifies the set of register files. The mapping between |
| // physreg and register files is done using a "register file mask". |
| // |
| // A register file mask identifies a set of register files. Each bit of the |
| // mask representation references a specific register file. |
| // For example: |
| // 0b0001 --> Register file #0 |
| // 0b0010 --> Register file #1 |
| // 0b0100 --> Register file #2 |
| // |
| // Note that this implementation allows register files to overlap. |
| // The maximum number of register files allowed by this implementation is 32. |
| using RegisterMapping = std::pair<WriteState *, unsigned>; |
| |
| // This map contains one entry for each physical register defined by the |
| // processor scheduling model. |
| std::vector<RegisterMapping> RegisterMappings; |
| |
| // This method creates a new RegisterMappingTracker for a register file that |
| // contains all the physical registers specified by the register classes in |
| // the 'RegisterClasses' set. |
| // |
| // The long term goal is to let scheduling models optionally describe register |
| // files via tablegen definitions. This is still a work in progress. |
| // For example, here is how a tablegen definition for a x86 FP register file |
| // that features AVX might look like: |
| // |
| // def FPRegisterFile : RegisterFile<[VR128RegClass, VR256RegClass], 60> |
| // |
| // Here FPRegisterFile contains all the registers defined by register class |
| // VR128RegClass and VR256RegClass. FPRegisterFile implements 60 |
| // registers which can be used for register renaming purpose. |
| // |
| // The list of register classes is then converted by the tablegen backend into |
| // a list of register class indices. That list, along with the number of |
| // available mappings, is then used to create a new RegisterMappingTracker. |
| void addRegisterFile(llvm::ArrayRef<unsigned> RegisterClasses, |
| unsigned NumTemps); |
| |
| // Allocates a new register mapping in every register file specified by the |
| // register file mask. This method is called from addRegisterMapping. |
| void createNewMappings(unsigned RegisterFileMask, |
| llvm::MutableArrayRef<unsigned> UsedPhysRegs); |
| |
| // Removes a previously allocated mapping from each register file in the |
| // RegisterFileMask set. This method is called from invalidateRegisterMapping. |
| void removeMappings(unsigned RegisterFileMask, |
| llvm::MutableArrayRef<unsigned> FreedPhysRegs); |
| |
| public: |
| RegisterFile(const llvm::MCRegisterInfo &mri, unsigned TempRegs = 0) |
| : MRI(mri), RegisterMappings(MRI.getNumRegs(), {nullptr, 0U}) { |
| addRegisterFile({}, TempRegs); |
| // TODO: teach the scheduling models how to specify multiple register files. |
| } |
| |
| // Creates a new register mapping for RegID. |
| // This reserves a microarchitectural register in every register file that |
| // contains RegID. |
| void addRegisterMapping(WriteState &WS, |
| llvm::MutableArrayRef<unsigned> UsedPhysRegs); |
| |
| // Invalidates register mappings associated to the input WriteState object. |
| // This releases previously allocated mappings for the physical register |
| // associated to the WriteState. |
| void invalidateRegisterMapping(const WriteState &WS, |
| llvm::MutableArrayRef<unsigned> FreedPhysRegs); |
| |
| // Checks if there are enough microarchitectural registers in the register |
| // files. Returns a "response mask" where each bit is the response from a |
| // RegisterMappingTracker. |
| // For example: if all register files are available, then the response mask |
| // is a bitmask of all zeroes. If Instead register file #1 is not available, |
| // then the response mask is 0b10. |
| unsigned isAvailable(llvm::ArrayRef<unsigned> Regs) const; |
| void collectWrites(llvm::SmallVectorImpl<WriteState *> &Writes, |
| unsigned RegID) const; |
| void updateOnRead(ReadState &RS, unsigned RegID); |
| |
| unsigned getNumRegisterFiles() const { return RegisterFiles.size(); } |
| |
| #ifndef NDEBUG |
| void dump() const; |
| #endif |
| }; |
| |
| /// \brief tracks which instructions are in-flight (i.e. dispatched but not |
| /// retired) in the OoO backend. |
| /// |
| /// This class checks on every cycle if/which instructions can be retired. |
| /// Instructions are retired in program order. |
| /// In the event of instruction retired, the DispatchUnit object that owns |
| /// this RetireControlUnit gets notified. |
| /// On instruction retired, register updates are all architecturally |
| /// committed, and any temporary registers originally allocated for the |
| /// retired instruction are freed. |
| struct RetireControlUnit { |
| // A "token" (object of class RUToken) is created by the retire unit for every |
| // instruction dispatched to the schedulers. Flag 'Executed' is used to |
| // quickly check if an instruction has reached the write-back stage. A token |
| // also carries information related to the number of entries consumed by the |
| // instruction in the reorder buffer. The idea is that those entries will |
| // become available again once the instruction is retired. On every cycle, |
| // the RCU (Retire Control Unit) scans every token starting to search for |
| // instructions that are ready to retire. retired. Instructions are retired |
| // in program order. Only 'Executed' instructions are eligible for retire. |
| // Note that the size of the reorder buffer is defined by the scheduling model |
| // via field 'NumMicroOpBufferSize'. |
| struct RUToken { |
| unsigned Index; // Instruction index. |
| unsigned NumSlots; // Slots reserved to this instruction. |
| bool Executed; // True if the instruction is past the WB stage. |
| }; |
| |
| private: |
| unsigned NextAvailableSlotIdx; |
| unsigned CurrentInstructionSlotIdx; |
| unsigned AvailableSlots; |
| unsigned MaxRetirePerCycle; // 0 means no limit. |
| std::vector<RUToken> Queue; |
| DispatchUnit *Owner; |
| |
| public: |
| RetireControlUnit(unsigned NumSlots, unsigned RPC, DispatchUnit *DU) |
| : NextAvailableSlotIdx(0), CurrentInstructionSlotIdx(0), |
| AvailableSlots(NumSlots), MaxRetirePerCycle(RPC), Owner(DU) { |
| assert(NumSlots && "Expected at least one slot!"); |
| Queue.resize(NumSlots); |
| } |
| |
| bool isFull() const { return !AvailableSlots; } |
| bool isEmpty() const { return AvailableSlots == Queue.size(); } |
| bool isAvailable(unsigned Quantity = 1) const { |
| // Some instructions may declare a number of uOps which exceedes the size |
| // of the reorder buffer. To avoid problems, cap the amount of slots to |
| // the size of the reorder buffer. |
| Quantity = std::min(Quantity, static_cast<unsigned>(Queue.size())); |
| return AvailableSlots >= Quantity; |
| } |
| |
| // Reserves a number of slots, and returns a new token. |
| unsigned reserveSlot(unsigned Index, unsigned NumMicroOps); |
| |
| /// Retires instructions in program order. |
| void cycleEvent(); |
| |
| void onInstructionExecuted(unsigned TokenID); |
| |
| #ifndef NDEBUG |
| void dump() const; |
| #endif |
| }; |
| |
| // \brief Implements the hardware dispatch logic. |
| // |
| // This class is responsible for the dispatch stage, in which instructions are |
| // dispatched in groups to the Scheduler. An instruction can be dispatched if |
| // functional units are available. |
| // To be more specific, an instruction can be dispatched to the Scheduler if: |
| // 1) There are enough entries in the reorder buffer (implemented by class |
| // RetireControlUnit) to accomodate all opcodes. |
| // 2) There are enough temporaries to rename output register operands. |
| // 3) There are enough entries available in the used buffered resource(s). |
| // |
| // The number of micro opcodes that can be dispatched in one cycle is limited by |
| // the value of field 'DispatchWidth'. A "dynamic dispatch stall" occurs when |
| // processor resources are not available (i.e. at least one of the |
| // abovementioned checks fails). Dispatch stall events are counted during the |
| // entire execution of the code, and displayed by the performance report when |
| // flag '-verbose' is specified. |
| // |
| // If the number of micro opcodes of an instruction is bigger than |
| // DispatchWidth, then it can only be dispatched at the beginning of one cycle. |
| // The DispatchUnit will still have to wait for a number of cycles (depending on |
| // the DispatchWidth and the number of micro opcodes) before it can serve other |
| // instructions. |
| class DispatchUnit { |
| unsigned DispatchWidth; |
| unsigned AvailableEntries; |
| unsigned CarryOver; |
| Scheduler *SC; |
| |
| std::unique_ptr<RegisterFile> RAT; |
| std::unique_ptr<RetireControlUnit> RCU; |
| Backend *Owner; |
| |
| bool checkRAT(unsigned Index, const Instruction &Desc); |
| bool checkRCU(unsigned Index, const InstrDesc &Desc); |
| bool checkScheduler(unsigned Index, const InstrDesc &Desc); |
| |
| void updateRAWDependencies(ReadState &RS, const llvm::MCSubtargetInfo &STI); |
| void notifyInstructionDispatched(unsigned IID, |
| llvm::ArrayRef<unsigned> UsedPhysRegs); |
| |
| public: |
| DispatchUnit(Backend *B, const llvm::MCRegisterInfo &MRI, |
| unsigned MicroOpBufferSize, unsigned RegisterFileSize, |
| unsigned MaxRetirePerCycle, unsigned MaxDispatchWidth, |
| Scheduler *Sched) |
| : DispatchWidth(MaxDispatchWidth), AvailableEntries(MaxDispatchWidth), |
| CarryOver(0U), SC(Sched), |
| RAT(llvm::make_unique<RegisterFile>(MRI, RegisterFileSize)), |
| RCU(llvm::make_unique<RetireControlUnit>(MicroOpBufferSize, |
| MaxRetirePerCycle, this)), |
| Owner(B) {} |
| |
| unsigned getDispatchWidth() const { return DispatchWidth; } |
| |
| bool isAvailable(unsigned NumEntries) const { |
| return NumEntries <= AvailableEntries || AvailableEntries == DispatchWidth; |
| } |
| |
| bool isRCUEmpty() const { return RCU->isEmpty(); } |
| |
| bool canDispatch(unsigned Index, const Instruction &Inst) { |
| const InstrDesc &Desc = Inst.getDesc(); |
| assert(isAvailable(Desc.NumMicroOps)); |
| return checkRCU(Index, Desc) && checkRAT(Index, Inst) && |
| checkScheduler(Index, Desc); |
| } |
| |
| void dispatch(unsigned IID, Instruction *I, const llvm::MCSubtargetInfo &STI); |
| |
| void collectWrites(llvm::SmallVectorImpl<WriteState *> &Vec, |
| unsigned RegID) const { |
| return RAT->collectWrites(Vec, RegID); |
| } |
| |
| void cycleEvent(unsigned Cycle) { |
| RCU->cycleEvent(); |
| AvailableEntries = |
| CarryOver >= DispatchWidth ? 0 : DispatchWidth - CarryOver; |
| CarryOver = CarryOver >= DispatchWidth ? CarryOver - DispatchWidth : 0U; |
| } |
| |
| void notifyInstructionRetired(unsigned Index); |
| |
| void notifyDispatchStall(unsigned Index, unsigned EventType); |
| |
| void onInstructionExecuted(unsigned TokenID) { |
| RCU->onInstructionExecuted(TokenID); |
| } |
| |
| #ifndef NDEBUG |
| void dump() const; |
| #endif |
| }; |
| } // namespace mca |
| |
| #endif |