inst_queue.hh revision 1684
19793Sakash.bagdia@arm.com#ifndef __CPU_BETA_CPU_INST_QUEUE_HH__ 27586SAli.Saidi@arm.com#define __CPU_BETA_CPU_INST_QUEUE_HH__ 37586SAli.Saidi@arm.com 47586SAli.Saidi@arm.com#include <list> 57586SAli.Saidi@arm.com#include <map> 67586SAli.Saidi@arm.com#include <queue> 77586SAli.Saidi@arm.com#include <stdint.h> 87586SAli.Saidi@arm.com#include <vector> 97586SAli.Saidi@arm.com 107586SAli.Saidi@arm.com#include "base/statistics.hh" 117586SAli.Saidi@arm.com#include "base/timebuf.hh" 127586SAli.Saidi@arm.com#include "cpu/inst_seq.hh" 133970Sgblack@eecs.umich.edu 143005Sstever@eecs.umich.edu/** 153005Sstever@eecs.umich.edu * A standard instruction queue class. It holds instructions in an 163005Sstever@eecs.umich.edu * array, holds the ordering of the instructions within a linked list, 173005Sstever@eecs.umich.edu * and tracks producer/consumer dependencies within a separate linked 183005Sstever@eecs.umich.edu * list. Similar to the rename map and the free list, it expects that 193005Sstever@eecs.umich.edu * floating point registers have their indices start after the integer 203005Sstever@eecs.umich.edu * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer 213005Sstever@eecs.umich.edu * and 96-191 are fp). This remains true even for both logical and 223005Sstever@eecs.umich.edu * physical register indices. 233005Sstever@eecs.umich.edu */ 243005Sstever@eecs.umich.edutemplate <class Impl> 253005Sstever@eecs.umich.educlass InstructionQueue 263005Sstever@eecs.umich.edu{ 273005Sstever@eecs.umich.edu public: 283005Sstever@eecs.umich.edu //Typedefs from the Impl. 293005Sstever@eecs.umich.edu typedef typename Impl::FullCPU FullCPU; 303005Sstever@eecs.umich.edu typedef typename Impl::DynInstPtr DynInstPtr; 313005Sstever@eecs.umich.edu typedef typename Impl::Params Params; 323005Sstever@eecs.umich.edu 333005Sstever@eecs.umich.edu typedef typename Impl::CPUPol::MemDepUnit MemDepUnit; 343005Sstever@eecs.umich.edu typedef typename Impl::CPUPol::IssueStruct IssueStruct; 353005Sstever@eecs.umich.edu typedef typename Impl::CPUPol::TimeStruct TimeStruct; 363005Sstever@eecs.umich.edu 373005Sstever@eecs.umich.edu // Typedef of iterator through the list of instructions. Might be 383005Sstever@eecs.umich.edu // better to untie this from the FullCPU or pass its information to 393005Sstever@eecs.umich.edu // the stages. 403005Sstever@eecs.umich.edu typedef typename std::list<DynInstPtr>::iterator ListIt; 416654Snate@binkert.org 426654Snate@binkert.org /** 432889SN/A * Struct for comparing entries to be added to the priority queue. This 442710SN/A * gives reverse ordering to the instructions in terms of sequence 456654Snate@binkert.org * numbers: the instructions with smaller sequence numbers (and hence 466654Snate@binkert.org * are older) will be at the top of the priority queue. 476654Snate@binkert.org */ 485457Ssaidi@eecs.umich.edu struct pqCompare 496654Snate@binkert.org { 506654Snate@binkert.org bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 512934SN/A { 522549SN/A return lhs->seqNum > rhs->seqNum; 532995SN/A } 543395Shsul@eecs.umich.edu }; 556981SLisa.Hsu@amd.com 563448Shsul@eecs.umich.edu /** 578920Snilay@cs.wisc.edu * Struct for comparing entries to be added to the set. This gives 583444Sktlim@umich.edu * standard ordering in terms of sequence numbers. 592889SN/A */ 608920Snilay@cs.wisc.edu struct setCompare 618920Snilay@cs.wisc.edu { 623322Shsul@eecs.umich.edu bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 632710SN/A { 642710SN/A return lhs->seqNum < rhs->seqNum; 652710SN/A } 662710SN/A }; 672710SN/A 682710SN/A typedef std::priority_queue<DynInstPtr, vector<DynInstPtr>, pqCompare> 693322Shsul@eecs.umich.edu ReadyInstQueue; 703304Sstever@eecs.umich.edu 713322Shsul@eecs.umich.edu InstructionQueue(Params ¶ms); 723322Shsul@eecs.umich.edu 733304Sstever@eecs.umich.edu void regStats(); 749653SAndreas.Sandberg@ARM.com 759653SAndreas.Sandberg@ARM.com void setCPU(FullCPU *cpu); 769653SAndreas.Sandberg@ARM.com 779653SAndreas.Sandberg@ARM.com void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue); 789653SAndreas.Sandberg@ARM.com 799653SAndreas.Sandberg@ARM.com void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr); 809653SAndreas.Sandberg@ARM.com 813481Shsul@eecs.umich.edu unsigned numFreeEntries(); 823481Shsul@eecs.umich.edu 832566SN/A bool isFull(); 849665Sandreas.hansson@arm.com 859665Sandreas.hansson@arm.com void insert(DynInstPtr &new_inst); 869665Sandreas.hansson@arm.com 879665Sandreas.hansson@arm.com void insertNonSpec(DynInstPtr &new_inst); 889665Sandreas.hansson@arm.com 892995SN/A void advanceTail(DynInstPtr &inst); 903304Sstever@eecs.umich.edu 913304Sstever@eecs.umich.edu void scheduleReadyInsts(); 923304Sstever@eecs.umich.edu 932995SN/A void scheduleNonSpec(const InstSeqNum &inst); 942995SN/A 952995SN/A void wakeDependents(DynInstPtr &completed_inst); 962917SN/A 972995SN/A void violation(DynInstPtr &store, DynInstPtr &faulting_load); 988956Sjayneel@cs.wisc.edu 992995SN/A // Change this to take in the sequence number 1008956Sjayneel@cs.wisc.edu void squash(); 1013304Sstever@eecs.umich.edu 1026135Sgblack@eecs.umich.edu void doSquash(); 1036135Sgblack@eecs.umich.edu 1046654Snate@binkert.org void stopSquash(); 1059665Sandreas.hansson@arm.com 1066654Snate@binkert.org private: 1079665Sandreas.hansson@arm.com /** Pointer to the CPU. */ 1086654Snate@binkert.org FullCPU *cpu; 1099665Sandreas.hansson@arm.com 1106654Snate@binkert.org /** The memory dependence unit, which tracks/predicts memory dependences 1119665Sandreas.hansson@arm.com * between instructions. 1129665Sandreas.hansson@arm.com */ 1137586SAli.Saidi@arm.com MemDepUnit memDepUnit; 1149665Sandreas.hansson@arm.com 1159665Sandreas.hansson@arm.com /** The queue to the execute stage. Issued instructions will be written 1169665Sandreas.hansson@arm.com * into it. 1173819Shsul@eecs.umich.edu */ 1189059Snilay@cs.wisc.edu TimeBuffer<IssueStruct> *issueToExecuteQueue; 1193819Shsul@eecs.umich.edu 1209793Sakash.bagdia@arm.com /** The backwards time buffer. */ 1219793Sakash.bagdia@arm.com TimeBuffer<TimeStruct> *timeBuffer; 1229793Sakash.bagdia@arm.com 1239793Sakash.bagdia@arm.com /** Wire to read information from timebuffer. */ 1249793Sakash.bagdia@arm.com typename TimeBuffer<TimeStruct>::wire fromCommit; 1259790Sakash.bagdia@arm.com 1263873Sbinkertn@umich.edu enum InstList { 1273873Sbinkertn@umich.edu Int, 1283873Sbinkertn@umich.edu Float, 1293873Sbinkertn@umich.edu Branch, 1303873Sbinkertn@umich.edu Memory, 1313873Sbinkertn@umich.edu Misc, 1328659SAli.Saidi@ARM.com Squashed, 1338659SAli.Saidi@ARM.com None 1349793Sakash.bagdia@arm.com }; 1359793Sakash.bagdia@arm.com 1369793Sakash.bagdia@arm.com /** List of ready int instructions. Used to keep track of the order in 1373668Srdreslin@umich.edu * which instructions should issue. 1389653SAndreas.Sandberg@ARM.com */ 1399653SAndreas.Sandberg@ARM.com ReadyInstQueue readyIntInsts; 1409653SAndreas.Sandberg@ARM.com 1416636Ssteve.reinhardt@amd.com /** List of ready floating point instructions. */ 1429788Sakash.bagdia@arm.com ReadyInstQueue readyFloatInsts; 1439788Sakash.bagdia@arm.com 1448839Sandreas.hansson@arm.com /** List of ready branch instructions. */ 1458839Sandreas.hansson@arm.com ReadyInstQueue readyBranchInsts; 1468713Sandreas.hansson@arm.com 1479408Sandreas.hansson@arm.com /** List of ready miscellaneous instructions. */ 1488839Sandreas.hansson@arm.com ReadyInstQueue readyMiscInsts; 1498839Sandreas.hansson@arm.com 1505142Ssaidi@eecs.umich.edu /** List of squashed instructions (which are still valid and in IQ). 1518926Sandreas.hansson@arm.com * Implemented using a priority queue; the entries must contain both 1529317Sandreas.hansson@arm.com * the IQ index and sequence number of each instruction so that 1539317Sandreas.hansson@arm.com * ordering based on sequence numbers can be used. 1549317Sandreas.hansson@arm.com */ 1559317Sandreas.hansson@arm.com ReadyInstQueue squashedInsts; 1569317Sandreas.hansson@arm.com 1578926Sandreas.hansson@arm.com /** List of non-speculative instructions that will be scheduled 1583312Sstever@eecs.umich.edu * once the IQ gets a signal from commit. While it's redundant to 1594968Sacolyte@umich.edu * have the key be a part of the value (the sequence number is stored 1608926Sandreas.hansson@arm.com * inside of DynInst), when these instructions are woken up only 1618887Sgeoffrey.blake@arm.com * the sequence number will be available. Thus it is most efficient to be 1628887Sgeoffrey.blake@arm.com * able to search by the sequence number alone. 1639384SAndreas.Sandberg@arm.com */ 1648887Sgeoffrey.blake@arm.com std::map<InstSeqNum, DynInstPtr> nonSpecInsts; 1658887Sgeoffrey.blake@arm.com 1664968Sacolyte@umich.edu typedef typename std::map<InstSeqNum, DynInstPtr>::iterator non_spec_it_t; 1673005Sstever@eecs.umich.edu 1686654Snate@binkert.org /** Number of free IQ entries left. */ 1699665Sandreas.hansson@arm.com unsigned freeEntries; 1706654Snate@binkert.org 1719665Sandreas.hansson@arm.com /** The number of entries in the instruction queue. */ 1726654Snate@binkert.org unsigned numEntries; 1739665Sandreas.hansson@arm.com 1746654Snate@binkert.org /** The number of integer instructions that can be issued in one 1759665Sandreas.hansson@arm.com * cycle. 1767586SAli.Saidi@arm.com */ 1779665Sandreas.hansson@arm.com unsigned intWidth; 1789665Sandreas.hansson@arm.com 1798661SAli.Saidi@ARM.com /** The number of floating point instructions that can be issued 1809793Sakash.bagdia@arm.com * in one cycle. 1819793Sakash.bagdia@arm.com */ 1829790Sakash.bagdia@arm.com unsigned floatWidth; 1839793Sakash.bagdia@arm.com 1849793Sakash.bagdia@arm.com /** The number of branches that can be issued in one cycle. */ 1859793Sakash.bagdia@arm.com unsigned branchWidth; 1869793Sakash.bagdia@arm.com 1879793Sakash.bagdia@arm.com /** The number of memory instructions that can be issued in one cycle. */ 1889384SAndreas.Sandberg@arm.com unsigned memoryWidth; 1898863Snilay@cs.wisc.edu 1907876Sgblack@eecs.umich.edu /** The total number of instructions that can be issued in one cycle. */ 1914968Sacolyte@umich.edu unsigned totalWidth; 1928926Sandreas.hansson@arm.com 1934837Ssaidi@eecs.umich.edu //The number of physical registers in the CPU. 1944837Ssaidi@eecs.umich.edu unsigned numPhysRegs; 1959408Sandreas.hansson@arm.com 1969653SAndreas.Sandberg@ARM.com /** The number of physical integer registers in the CPU. */ 1979653SAndreas.Sandberg@ARM.com unsigned numPhysIntRegs; 1989653SAndreas.Sandberg@ARM.com 1999164Sandreas.hansson@arm.com /** The number of floating point registers in the CPU. */ 2009408Sandreas.hansson@arm.com unsigned numPhysFloatRegs; 2018845Sandreas.hansson@arm.com 2028845Sandreas.hansson@arm.com /** Delay between commit stage and the IQ. 2034837Ssaidi@eecs.umich.edu * @todo: Make there be a distinction between the delays within IEW. 2048659SAli.Saidi@ARM.com */ 2058801Sgblack@eecs.umich.edu unsigned commitToIEWDelay; 2063005Sstever@eecs.umich.edu 2078801Sgblack@eecs.umich.edu ////////////////////////////////// 2083005Sstever@eecs.umich.edu // Variables needed for squashing 2093005Sstever@eecs.umich.edu ////////////////////////////////// 2103005Sstever@eecs.umich.edu 2112566SN/A /** The sequence number of the squashed instruction. */ 2127861Sgblack@eecs.umich.edu InstSeqNum squashedSeqNum; 2137861Sgblack@eecs.umich.edu 2147861Sgblack@eecs.umich.edu /** Iterator that points to the youngest instruction in the IQ. */ 2158635Schris.emmons@arm.com ListIt tail; 2168635Schris.emmons@arm.com 2178635Schris.emmons@arm.com /** Iterator that points to the last instruction that has been squashed. 2189061Snilay@cs.wisc.edu * This will not be valid unless the IQ is in the process of squashing. 2193481Shsul@eecs.umich.edu */ 220 ListIt squashIt; 221 222 /////////////////////////////////// 223 // Dependency graph stuff 224 /////////////////////////////////// 225 226 class DependencyEntry 227 { 228 public: 229 DynInstPtr inst; 230 //Might want to include data about what arch. register the 231 //dependence is waiting on. 232 DependencyEntry *next; 233 234 //This function, and perhaps this whole class, stand out a little 235 //bit as they don't fit a classification well. I want access 236 //to the underlying structure of the linked list, yet at 237 //the same time it feels like this should be something abstracted 238 //away. So for now it will sit here, within the IQ, until 239 //a better implementation is decided upon. 240 // This function probably shouldn't be within the entry... 241 void insert(DynInstPtr &new_inst); 242 243 void remove(DynInstPtr &inst_to_remove); 244 245 // Debug variable, remove when done testing. 246 static unsigned mem_alloc_counter; 247 }; 248 249 /** Array of linked lists. Each linked list is a list of all the 250 * instructions that depend upon a given register. The actual 251 * register's index is used to index into the graph; ie all 252 * instructions in flight that are dependent upon r34 will be 253 * in the linked list of dependGraph[34]. 254 */ 255 DependencyEntry *dependGraph; 256 257 /** A cache of the recently woken registers. It is 1 if the register 258 * has been woken up recently, and 0 if the register has been added 259 * to the dependency graph and has not yet received its value. It 260 * is basically a secondary scoreboard, and should pretty much mirror 261 * the scoreboard that exists in the rename map. 262 */ 263 vector<bool> regScoreboard; 264 265 bool addToDependents(DynInstPtr &new_inst); 266 void insertDependency(DynInstPtr &new_inst); 267 void createDependency(DynInstPtr &new_inst); 268 269 void addIfReady(DynInstPtr &inst); 270 271 private: 272 /** Debugging function to count how many entries are in the IQ. It does 273 * a linear walk through the instructions, so do not call this function 274 * during normal execution. 275 */ 276 int countInsts(); 277 278 /** Debugging function to dump out the dependency graph. 279 */ 280 void dumpDependGraph(); 281 282 /** Debugging function to dump all the list sizes, as well as print 283 * out the list of nonspeculative instructions. Should not be used 284 * in any other capacity, but it has no harmful sideaffects. 285 */ 286 void dumpLists(); 287 288 Stats::Scalar<> iqInstsAdded; 289 Stats::Scalar<> iqNonSpecInstsAdded; 290// Stats::Scalar<> iqIntInstsAdded; 291 Stats::Scalar<> iqIntInstsIssued; 292// Stats::Scalar<> iqFloatInstsAdded; 293 Stats::Scalar<> iqFloatInstsIssued; 294// Stats::Scalar<> iqBranchInstsAdded; 295 Stats::Scalar<> iqBranchInstsIssued; 296// Stats::Scalar<> iqMemInstsAdded; 297 Stats::Scalar<> iqMemInstsIssued; 298// Stats::Scalar<> iqMiscInstsAdded; 299 Stats::Scalar<> iqMiscInstsIssued; 300 Stats::Scalar<> iqSquashedInstsIssued; 301 Stats::Scalar<> iqLoopSquashStalls; 302 Stats::Scalar<> iqSquashedInstsExamined; 303 Stats::Scalar<> iqSquashedOperandsExamined; 304 Stats::Scalar<> iqSquashedNonSpecRemoved; 305 306}; 307 308#endif //__CPU_BETA_CPU_INST_QUEUE_HH__ 309