inst_queue.hh revision 1681
12810SN/A#ifndef __INST_QUEUE_HH__ 212724Snikos.nikoleris@arm.com#define __INST_QUEUE_HH__ 38856Sandreas.hansson@arm.com 48856Sandreas.hansson@arm.com#include <list> 58856Sandreas.hansson@arm.com#include <map> 68856Sandreas.hansson@arm.com#include <queue> 78856Sandreas.hansson@arm.com#include <stdint.h> 88856Sandreas.hansson@arm.com#include <vector> 98856Sandreas.hansson@arm.com 108856Sandreas.hansson@arm.com#include "base/statistics.hh" 118856Sandreas.hansson@arm.com#include "base/timebuf.hh" 128856Sandreas.hansson@arm.com#include "cpu/inst_seq.hh" 138856Sandreas.hansson@arm.com 142810SN/A/** 152810SN/A * A standard instruction queue class. It holds instructions in an 162810SN/A * array, holds the ordering of the instructions within a linked list, 172810SN/A * and tracks producer/consumer dependencies within a separate linked 182810SN/A * list. Similar to the rename map and the free list, it expects that 192810SN/A * floating point registers have their indices start after the integer 202810SN/A * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer 212810SN/A * and 96-191 are fp). This remains true even for both logical and 222810SN/A * physical register indices. 232810SN/A */ 242810SN/Atemplate <class Impl> 252810SN/Aclass InstructionQueue 262810SN/A{ 272810SN/A public: 282810SN/A //Typedefs from the Impl. 292810SN/A typedef typename Impl::FullCPU FullCPU; 302810SN/A typedef typename Impl::DynInstPtr DynInstPtr; 312810SN/A typedef typename Impl::Params Params; 322810SN/A 332810SN/A typedef typename Impl::CPUPol::MemDepUnit MemDepUnit; 342810SN/A typedef typename Impl::CPUPol::IssueStruct IssueStruct; 352810SN/A typedef typename Impl::CPUPol::TimeStruct TimeStruct; 362810SN/A 372810SN/A // Typedef of iterator through the list of instructions. Might be 382810SN/A // better to untie this from the FullCPU or pass its information to 392810SN/A // the stages. 402810SN/A typedef typename std::list<DynInstPtr>::iterator ListIt; 4112724Snikos.nikoleris@arm.com 422810SN/A /** 432810SN/A * Struct for comparing entries to be added to the priority queue. This 442810SN/A * gives reverse ordering to the instructions in terms of sequence 452810SN/A * numbers: the instructions with smaller sequence numbers (and hence 462810SN/A * are older) will be at the top of the priority queue. 472810SN/A */ 482810SN/A struct pqCompare 4911486Snikos.nikoleris@arm.com { 5011486Snikos.nikoleris@arm.com bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 5112724Snikos.nikoleris@arm.com { 5212724Snikos.nikoleris@arm.com return lhs->seqNum > rhs->seqNum; 538232Snate@binkert.org } 5412724Snikos.nikoleris@arm.com }; 5513222Sodanrc@yahoo.com.br 5612724Snikos.nikoleris@arm.com /** 5711486Snikos.nikoleris@arm.com * Struct for comparing entries to be added to the set. This gives 5812724Snikos.nikoleris@arm.com * standard ordering in terms of sequence numbers. 5912724Snikos.nikoleris@arm.com */ 6012724Snikos.nikoleris@arm.com struct setCompare 6113352Snikos.nikoleris@arm.com { 6212724Snikos.nikoleris@arm.com bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 6312724Snikos.nikoleris@arm.com { 6412724Snikos.nikoleris@arm.com return lhs->seqNum < rhs->seqNum; 6512724Snikos.nikoleris@arm.com } 662810SN/A }; 672810SN/A 682810SN/A typedef std::priority_queue<DynInstPtr, vector<DynInstPtr>, pqCompare> 698856Sandreas.hansson@arm.com ReadyInstQueue; 708856Sandreas.hansson@arm.com 718856Sandreas.hansson@arm.com InstructionQueue(Params ¶ms); 7213564Snikos.nikoleris@arm.com 7313564Snikos.nikoleris@arm.com void regStats(); 7412084Sspwilson2@wisc.edu 7512084Sspwilson2@wisc.edu void setCPU(FullCPU *cpu); 768856Sandreas.hansson@arm.com 778856Sandreas.hansson@arm.com void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue); 784475SN/A 7911053Sandreas.hansson@arm.com void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr); 805034SN/A 8112724Snikos.nikoleris@arm.com unsigned numFreeEntries(); 8212724Snikos.nikoleris@arm.com 8311377Sandreas.hansson@arm.com bool isFull(); 8411377Sandreas.hansson@arm.com 8512724Snikos.nikoleris@arm.com void insert(DynInstPtr &new_inst); 8612724Snikos.nikoleris@arm.com 8713352Snikos.nikoleris@arm.com void insertNonSpec(DynInstPtr &new_inst); 8812724Snikos.nikoleris@arm.com 8912724Snikos.nikoleris@arm.com void advanceTail(DynInstPtr &inst); 9012724Snikos.nikoleris@arm.com 9112724Snikos.nikoleris@arm.com void scheduleReadyInsts(); 9212724Snikos.nikoleris@arm.com 9311053Sandreas.hansson@arm.com void scheduleNonSpec(const InstSeqNum &inst); 9411722Ssophiane.senni@gmail.com 9511722Ssophiane.senni@gmail.com void wakeDependents(DynInstPtr &completed_inst); 9611722Ssophiane.senni@gmail.com 9711722Ssophiane.senni@gmail.com void violation(DynInstPtr &store, DynInstPtr &faulting_load); 989263Smrinmoy.ghosh@arm.com 9913418Sodanrc@yahoo.com.br // Change this to take in the sequence number 1005034SN/A void squash(); 10111331Sandreas.hansson@arm.com 10212724Snikos.nikoleris@arm.com void doSquash(); 10310884Sandreas.hansson@arm.com 1044626SN/A void stopSquash(); 10510360Sandreas.hansson@arm.com 10611484Snikos.nikoleris@arm.com /** Debugging function to dump all the list sizes, as well as print 1075034SN/A * out the list of nonspeculative instructions. Should not be used 1088883SAli.Saidi@ARM.com * in any other capacity, but it has no harmful sideaffects. 1098833Sdam.sunwoo@arm.com */ 1104458SN/A void dumpLists(); 11111377Sandreas.hansson@arm.com 11211377Sandreas.hansson@arm.com private: 11311377Sandreas.hansson@arm.com /** Debugging function to count how many entries are in the IQ. It does 11411377Sandreas.hansson@arm.com * a linear walk through the instructions, so do not call this function 11511377Sandreas.hansson@arm.com * during normal execution. 11611377Sandreas.hansson@arm.com */ 11711331Sandreas.hansson@arm.com int countInsts(); 11811331Sandreas.hansson@arm.com 11912724Snikos.nikoleris@arm.com private: 12012843Srmk35@cl.cam.ac.uk /** Pointer to the CPU. */ 12112724Snikos.nikoleris@arm.com FullCPU *cpu; 12213419Sodanrc@yahoo.com.br 12312724Snikos.nikoleris@arm.com /** The memory dependence unit, which tracks/predicts memory dependences 12412724Snikos.nikoleris@arm.com * between instructions. 12512724Snikos.nikoleris@arm.com */ 12612724Snikos.nikoleris@arm.com MemDepUnit memDepUnit; 12712724Snikos.nikoleris@arm.com 12812724Snikos.nikoleris@arm.com /** The queue to the execute stage. Issued instructions will be written 12912724Snikos.nikoleris@arm.com * into it. 1302810SN/A */ 1312810SN/A TimeBuffer<IssueStruct> *issueToExecuteQueue; 1323013SN/A 1338856Sandreas.hansson@arm.com /** The backwards time buffer. */ 1342810SN/A TimeBuffer<TimeStruct> *timeBuffer; 1353013SN/A 13610714Sandreas.hansson@arm.com /** Wire to read information from timebuffer. */ 1372810SN/A typename TimeBuffer<TimeStruct>::wire fromCommit; 1389614Srene.dejong@arm.com 1399614Srene.dejong@arm.com enum InstList { 1409614Srene.dejong@arm.com Int, 14110345SCurtis.Dunham@arm.com Float, 14210714Sandreas.hansson@arm.com Branch, 14310345SCurtis.Dunham@arm.com Memory, 1449614Srene.dejong@arm.com Misc, 1452810SN/A Squashed, 1462810SN/A None 1472810SN/A }; 1488856Sandreas.hansson@arm.com 1492810SN/A /** List of ready int instructions. Used to keep track of the order in 1503013SN/A * which instructions should issue. 15110714Sandreas.hansson@arm.com */ 1523013SN/A ReadyInstQueue readyIntInsts; 1538856Sandreas.hansson@arm.com 15410714Sandreas.hansson@arm.com /** List of ready floating point instructions. */ 1558922Swilliam.wang@arm.com ReadyInstQueue readyFloatInsts; 1562897SN/A 1572810SN/A /** List of ready branch instructions. */ 1582810SN/A ReadyInstQueue readyBranchInsts; 15910344Sandreas.hansson@arm.com 16010344Sandreas.hansson@arm.com /** List of ready memory instructions. */ 16110344Sandreas.hansson@arm.com// ReadyInstQueue readyMemInsts; 16210714Sandreas.hansson@arm.com 16310344Sandreas.hansson@arm.com /** List of ready miscellaneous instructions. */ 16410344Sandreas.hansson@arm.com ReadyInstQueue readyMiscInsts; 16510344Sandreas.hansson@arm.com 16610713Sandreas.hansson@arm.com /** List of squashed instructions (which are still valid and in IQ). 16710344Sandreas.hansson@arm.com * Implemented using a priority queue; the entries must contain both 1682844SN/A * the IQ index and sequence number of each instruction so that 16912730Sodanrc@yahoo.com.br * ordering based on sequence numbers can be used. 17012730Sodanrc@yahoo.com.br */ 17112730Sodanrc@yahoo.com.br ReadyInstQueue squashedInsts; 17212730Sodanrc@yahoo.com.br 17312730Sodanrc@yahoo.com.br /** List of non-speculative instructions that will be scheduled 17412730Sodanrc@yahoo.com.br * once the IQ gets a signal from commit. While it's redundant to 17512730Sodanrc@yahoo.com.br * have the key be a part of the value (the sequence number is stored 17612730Sodanrc@yahoo.com.br * inside of DynInst), when these instructions are woken up only 17712730Sodanrc@yahoo.com.br * the sequence number will be available. Thus it is most efficient to be 17812730Sodanrc@yahoo.com.br * able to search by the sequence number alone. 1792810SN/A */ 1802858SN/A std::map<InstSeqNum, DynInstPtr> nonSpecInsts; 1812858SN/A 18212724Snikos.nikoleris@arm.com typedef typename std::map<InstSeqNum, DynInstPtr>::iterator non_spec_it_t; 1838922Swilliam.wang@arm.com 18412724Snikos.nikoleris@arm.com /** Number of free IQ entries left. */ 18512724Snikos.nikoleris@arm.com unsigned freeEntries; 1862858SN/A 1872858SN/A /** The number of entries in the instruction queue. */ 1889294Sandreas.hansson@arm.com unsigned numEntries; 1899294Sandreas.hansson@arm.com 1908922Swilliam.wang@arm.com /** The number of integer instructions that can be issued in one 1918922Swilliam.wang@arm.com * cycle. 19212724Snikos.nikoleris@arm.com */ 1938922Swilliam.wang@arm.com unsigned intWidth; 1948922Swilliam.wang@arm.com 1958922Swilliam.wang@arm.com /** The number of floating point instructions that can be issued 1968922Swilliam.wang@arm.com * in one cycle. 1978922Swilliam.wang@arm.com */ 1989294Sandreas.hansson@arm.com unsigned floatWidth; 1999294Sandreas.hansson@arm.com 2008922Swilliam.wang@arm.com /** The number of branches that can be issued in one cycle. */ 2018922Swilliam.wang@arm.com unsigned branchWidth; 20212724Snikos.nikoleris@arm.com 2038922Swilliam.wang@arm.com /** The number of memory instructions that can be issued in one cycle. */ 2048922Swilliam.wang@arm.com unsigned memoryWidth; 2058922Swilliam.wang@arm.com 2068922Swilliam.wang@arm.com /** The total number of instructions that can be issued in one cycle. */ 2074628SN/A unsigned totalWidth; 20810821Sandreas.hansson@arm.com 20910821Sandreas.hansson@arm.com //The number of physical registers in the CPU. 21010821Sandreas.hansson@arm.com unsigned numPhysRegs; 21110821Sandreas.hansson@arm.com 21210821Sandreas.hansson@arm.com /** The number of physical integer registers in the CPU. */ 21310821Sandreas.hansson@arm.com unsigned numPhysIntRegs; 21410821Sandreas.hansson@arm.com 21510821Sandreas.hansson@arm.com /** The number of floating point registers in the CPU. */ 21610821Sandreas.hansson@arm.com unsigned numPhysFloatRegs; 21710821Sandreas.hansson@arm.com 21810821Sandreas.hansson@arm.com /** Delay between commit stage and the IQ. 2192858SN/A * @todo: Make there be a distinction between the delays within IEW. 22012724Snikos.nikoleris@arm.com */ 22112724Snikos.nikoleris@arm.com unsigned commitToIEWDelay; 22212724Snikos.nikoleris@arm.com 22313745Sodanrc@yahoo.com.br ////////////////////////////////// 22413745Sodanrc@yahoo.com.br // Variables needed for squashing 22513745Sodanrc@yahoo.com.br ////////////////////////////////// 22613745Sodanrc@yahoo.com.br 22712724Snikos.nikoleris@arm.com /** The sequence number of the squashed instruction. */ 22812724Snikos.nikoleris@arm.com InstSeqNum squashedSeqNum; 22912724Snikos.nikoleris@arm.com 23012724Snikos.nikoleris@arm.com /** Iterator that points to the youngest instruction in the IQ. */ 23112724Snikos.nikoleris@arm.com ListIt tail; 23213418Sodanrc@yahoo.com.br 23313418Sodanrc@yahoo.com.br /** Iterator that points to the last instruction that has been squashed. 23413564Snikos.nikoleris@arm.com * This will not be valid unless the IQ is in the process of squashing. 23512724Snikos.nikoleris@arm.com */ 23612724Snikos.nikoleris@arm.com ListIt squashIt; 23712724Snikos.nikoleris@arm.com 23812724Snikos.nikoleris@arm.com /////////////////////////////////// 23912724Snikos.nikoleris@arm.com // Dependency graph stuff 24012724Snikos.nikoleris@arm.com /////////////////////////////////// 24112724Snikos.nikoleris@arm.com 24212724Snikos.nikoleris@arm.com class DependencyEntry 24312724Snikos.nikoleris@arm.com { 24412724Snikos.nikoleris@arm.com public: 24512724Snikos.nikoleris@arm.com DynInstPtr inst; 24612724Snikos.nikoleris@arm.com //Might want to include data about what arch. register the 24712724Snikos.nikoleris@arm.com //dependence is waiting on. 24812724Snikos.nikoleris@arm.com DependencyEntry *next; 24912724Snikos.nikoleris@arm.com 25012724Snikos.nikoleris@arm.com //This function, and perhaps this whole class, stand out a little 25113352Snikos.nikoleris@arm.com //bit as they don't fit a classification well. I want access 25213352Snikos.nikoleris@arm.com //to the underlying structure of the linked list, yet at 25313352Snikos.nikoleris@arm.com //the same time it feels like this should be something abstracted 25413352Snikos.nikoleris@arm.com //away. So for now it will sit here, within the IQ, until 25513352Snikos.nikoleris@arm.com //a better implementation is decided upon. 25613352Snikos.nikoleris@arm.com // This function probably shouldn't be within the entry... 25712724Snikos.nikoleris@arm.com void insert(DynInstPtr &new_inst); 25812724Snikos.nikoleris@arm.com 25912724Snikos.nikoleris@arm.com void remove(DynInstPtr &inst_to_remove); 26012724Snikos.nikoleris@arm.com 26112724Snikos.nikoleris@arm.com // Debug variable, remove when done testing. 26212724Snikos.nikoleris@arm.com static unsigned mem_alloc_counter; 26312724Snikos.nikoleris@arm.com }; 26412724Snikos.nikoleris@arm.com 26512724Snikos.nikoleris@arm.com /** Array of linked lists. Each linked list is a list of all the 26612724Snikos.nikoleris@arm.com * instructions that depend upon a given register. The actual 26712724Snikos.nikoleris@arm.com * register's index is used to index into the graph; ie all 26812724Snikos.nikoleris@arm.com * instructions in flight that are dependent upon r34 will be 26912724Snikos.nikoleris@arm.com * in the linked list of dependGraph[34]. 27012724Snikos.nikoleris@arm.com */ 27112724Snikos.nikoleris@arm.com DependencyEntry *dependGraph; 27212724Snikos.nikoleris@arm.com 27312724Snikos.nikoleris@arm.com /** A cache of the recently woken registers. It is 1 if the register 27412724Snikos.nikoleris@arm.com * has been woken up recently, and 0 if the register has been added 27512724Snikos.nikoleris@arm.com * to the dependency graph and has not yet received its value. It 27612724Snikos.nikoleris@arm.com * is basically a secondary scoreboard, and should pretty much mirror 27712724Snikos.nikoleris@arm.com * the scoreboard that exists in the rename map. 27812724Snikos.nikoleris@arm.com */ 27912724Snikos.nikoleris@arm.com vector<bool> regScoreboard; 28012724Snikos.nikoleris@arm.com 28112724Snikos.nikoleris@arm.com bool addToDependents(DynInstPtr &new_inst); 28212724Snikos.nikoleris@arm.com void insertDependency(DynInstPtr &new_inst); 28312724Snikos.nikoleris@arm.com void createDependency(DynInstPtr &new_inst); 28412724Snikos.nikoleris@arm.com void dumpDependGraph(); 28512724Snikos.nikoleris@arm.com 28612724Snikos.nikoleris@arm.com void addIfReady(DynInstPtr &inst); 28712724Snikos.nikoleris@arm.com 28812724Snikos.nikoleris@arm.com Stats::Scalar<> iqInstsAdded; 28912724Snikos.nikoleris@arm.com Stats::Scalar<> iqNonSpecInstsAdded; 29012724Snikos.nikoleris@arm.com// Stats::Scalar<> iqIntInstsAdded; 29112724Snikos.nikoleris@arm.com Stats::Scalar<> iqIntInstsIssued; 29212724Snikos.nikoleris@arm.com// Stats::Scalar<> iqFloatInstsAdded; 29312724Snikos.nikoleris@arm.com Stats::Scalar<> iqFloatInstsIssued; 29412724Snikos.nikoleris@arm.com// Stats::Scalar<> iqBranchInstsAdded; 29512724Snikos.nikoleris@arm.com Stats::Scalar<> iqBranchInstsIssued; 29612724Snikos.nikoleris@arm.com// Stats::Scalar<> iqMemInstsAdded; 29712724Snikos.nikoleris@arm.com Stats::Scalar<> iqMemInstsIssued; 29812724Snikos.nikoleris@arm.com// Stats::Scalar<> iqMiscInstsAdded; 29912724Snikos.nikoleris@arm.com Stats::Scalar<> iqMiscInstsIssued; 30012724Snikos.nikoleris@arm.com Stats::Scalar<> iqSquashedInstsIssued; 30112724Snikos.nikoleris@arm.com Stats::Scalar<> iqLoopSquashStalls; 30212724Snikos.nikoleris@arm.com Stats::Scalar<> iqSquashedInstsExamined; 30312724Snikos.nikoleris@arm.com Stats::Scalar<> iqSquashedOperandsExamined; 30412724Snikos.nikoleris@arm.com Stats::Scalar<> iqSquashedNonSpecRemoved; 30512724Snikos.nikoleris@arm.com 30612724Snikos.nikoleris@arm.com}; 30712724Snikos.nikoleris@arm.com 30812724Snikos.nikoleris@arm.com#endif //__INST_QUEUE_HH__ 30912724Snikos.nikoleris@arm.com