inst_queue.hh revision 1684
12553SN/A#ifndef __CPU_BETA_CPU_INST_QUEUE_HH__ 22553SN/A#define __CPU_BETA_CPU_INST_QUEUE_HH__ 32553SN/A 42553SN/A#include <list> 52553SN/A#include <map> 62553SN/A#include <queue> 72553SN/A#include <stdint.h> 82553SN/A#include <vector> 92553SN/A 102553SN/A#include "base/statistics.hh" 112553SN/A#include "base/timebuf.hh" 122553SN/A#include "cpu/inst_seq.hh" 132553SN/A 142553SN/A/** 152553SN/A * A standard instruction queue class. It holds instructions in an 162553SN/A * array, holds the ordering of the instructions within a linked list, 172553SN/A * and tracks producer/consumer dependencies within a separate linked 182553SN/A * list. Similar to the rename map and the free list, it expects that 192553SN/A * floating point registers have their indices start after the integer 202553SN/A * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer 212553SN/A * and 96-191 are fp). This remains true even for both logical and 222553SN/A * physical register indices. 232553SN/A */ 242553SN/Atemplate <class Impl> 252553SN/Aclass InstructionQueue 262553SN/A{ 272665Ssaidi@eecs.umich.edu public: 282665Ssaidi@eecs.umich.edu //Typedefs from the Impl. 292553SN/A typedef typename Impl::FullCPU FullCPU; 302553SN/A typedef typename Impl::DynInstPtr DynInstPtr; 315569Snate@binkert.org typedef typename Impl::Params Params; 325569Snate@binkert.org 332553SN/A typedef typename Impl::CPUPol::MemDepUnit MemDepUnit; 342553SN/A typedef typename Impl::CPUPol::IssueStruct IssueStruct; 352553SN/A typedef typename Impl::CPUPol::TimeStruct TimeStruct; 362553SN/A 372553SN/A // Typedef of iterator through the list of instructions. Might be 382553SN/A // better to untie this from the FullCPU or pass its information to 392553SN/A // the stages. 402553SN/A typedef typename std::list<DynInstPtr>::iterator ListIt; 412553SN/A 422553SN/A /** 432553SN/A * Struct for comparing entries to be added to the priority queue. This 442553SN/A * gives reverse ordering to the instructions in terms of sequence 452553SN/A * numbers: the instructions with smaller sequence numbers (and hence 462553SN/A * are older) will be at the top of the priority queue. 472553SN/A */ 482553SN/A struct pqCompare 492553SN/A { 502553SN/A bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 512553SN/A { 522553SN/A return lhs->seqNum > rhs->seqNum; 535543Ssaidi@eecs.umich.edu } 545543Ssaidi@eecs.umich.edu }; 555543Ssaidi@eecs.umich.edu 565543Ssaidi@eecs.umich.edu /** 575543Ssaidi@eecs.umich.edu * Struct for comparing entries to be added to the set. This gives 585543Ssaidi@eecs.umich.edu * standard ordering in terms of sequence numbers. 595543Ssaidi@eecs.umich.edu */ 605543Ssaidi@eecs.umich.edu struct setCompare 615543Ssaidi@eecs.umich.edu { 625543Ssaidi@eecs.umich.edu bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 635543Ssaidi@eecs.umich.edu { 645543Ssaidi@eecs.umich.edu return lhs->seqNum < rhs->seqNum; 655543Ssaidi@eecs.umich.edu } 665543Ssaidi@eecs.umich.edu }; 675543Ssaidi@eecs.umich.edu 682553SN/A typedef std::priority_queue<DynInstPtr, vector<DynInstPtr>, pqCompare> 692553SN/A ReadyInstQueue; 702553SN/A 712553SN/A InstructionQueue(Params ¶ms); 722553SN/A 732553SN/A void regStats(); 742553SN/A 755569Snate@binkert.org void setCPU(FullCPU *cpu); 765569Snate@binkert.org 775569Snate@binkert.org void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue); 785569Snate@binkert.org 795569Snate@binkert.org void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr); 805569Snate@binkert.org 815569Snate@binkert.org unsigned numFreeEntries(); 822555SN/A 832553SN/A bool isFull(); 842553SN/A 852553SN/A void insert(DynInstPtr &new_inst); 862553SN/A 872553SN/A void insertNonSpec(DynInstPtr &new_inst); 882553SN/A 892553SN/A void advanceTail(DynInstPtr &inst); 902553SN/A 912553SN/A void scheduleReadyInsts(); 922553SN/A 932553SN/A void scheduleNonSpec(const InstSeqNum &inst); 942553SN/A 952553SN/A void wakeDependents(DynInstPtr &completed_inst); 962553SN/A 972553SN/A void violation(DynInstPtr &store, DynInstPtr &faulting_load); 982553SN/A 994131Sbinkertn@umich.edu // Change this to take in the sequence number 1004131Sbinkertn@umich.edu void squash(); 1014131Sbinkertn@umich.edu 1024131Sbinkertn@umich.edu void doSquash(); 1034131Sbinkertn@umich.edu 1044131Sbinkertn@umich.edu void stopSquash(); 1054131Sbinkertn@umich.edu 1064131Sbinkertn@umich.edu private: 1074131Sbinkertn@umich.edu /** Pointer to the CPU. */ 1082553SN/A FullCPU *cpu; 1092553SN/A 1102553SN/A /** The memory dependence unit, which tracks/predicts memory dependences 1112553SN/A * between instructions. 1122555SN/A */ 1132555SN/A MemDepUnit memDepUnit; 1142555SN/A 1152555SN/A /** The queue to the execute stage. Issued instructions will be written 1162555SN/A * into it. 1172555SN/A */ 1182555SN/A TimeBuffer<IssueStruct> *issueToExecuteQueue; 1192555SN/A 1202555SN/A /** The backwards time buffer. */ 1212555SN/A TimeBuffer<TimeStruct> *timeBuffer; 1222555SN/A 1232555SN/A /** Wire to read information from timebuffer. */ 1242555SN/A typename TimeBuffer<TimeStruct>::wire fromCommit; 1252555SN/A 1262555SN/A enum InstList { 1272555SN/A Int, 1282553SN/A Float, 1292553SN/A Branch, 1305569Snate@binkert.org Memory, 131 Misc, 132 Squashed, 133 None 134 }; 135 136 /** List of ready int instructions. Used to keep track of the order in 137 * which instructions should issue. 138 */ 139 ReadyInstQueue readyIntInsts; 140 141 /** List of ready floating point instructions. */ 142 ReadyInstQueue readyFloatInsts; 143 144 /** List of ready branch instructions. */ 145 ReadyInstQueue readyBranchInsts; 146 147 /** List of ready miscellaneous instructions. */ 148 ReadyInstQueue readyMiscInsts; 149 150 /** List of squashed instructions (which are still valid and in IQ). 151 * Implemented using a priority queue; the entries must contain both 152 * the IQ index and sequence number of each instruction so that 153 * ordering based on sequence numbers can be used. 154 */ 155 ReadyInstQueue squashedInsts; 156 157 /** List of non-speculative instructions that will be scheduled 158 * once the IQ gets a signal from commit. While it's redundant to 159 * have the key be a part of the value (the sequence number is stored 160 * inside of DynInst), when these instructions are woken up only 161 * the sequence number will be available. Thus it is most efficient to be 162 * able to search by the sequence number alone. 163 */ 164 std::map<InstSeqNum, DynInstPtr> nonSpecInsts; 165 166 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator non_spec_it_t; 167 168 /** Number of free IQ entries left. */ 169 unsigned freeEntries; 170 171 /** The number of entries in the instruction queue. */ 172 unsigned numEntries; 173 174 /** The number of integer instructions that can be issued in one 175 * cycle. 176 */ 177 unsigned intWidth; 178 179 /** The number of floating point instructions that can be issued 180 * in one cycle. 181 */ 182 unsigned floatWidth; 183 184 /** The number of branches that can be issued in one cycle. */ 185 unsigned branchWidth; 186 187 /** The number of memory instructions that can be issued in one cycle. */ 188 unsigned memoryWidth; 189 190 /** The total number of instructions that can be issued in one cycle. */ 191 unsigned totalWidth; 192 193 //The number of physical registers in the CPU. 194 unsigned numPhysRegs; 195 196 /** The number of physical integer registers in the CPU. */ 197 unsigned numPhysIntRegs; 198 199 /** The number of floating point registers in the CPU. */ 200 unsigned numPhysFloatRegs; 201 202 /** Delay between commit stage and the IQ. 203 * @todo: Make there be a distinction between the delays within IEW. 204 */ 205 unsigned commitToIEWDelay; 206 207 ////////////////////////////////// 208 // Variables needed for squashing 209 ////////////////////////////////// 210 211 /** The sequence number of the squashed instruction. */ 212 InstSeqNum squashedSeqNum; 213 214 /** Iterator that points to the youngest instruction in the IQ. */ 215 ListIt tail; 216 217 /** Iterator that points to the last instruction that has been squashed. 218 * This will not be valid unless the IQ is in the process of squashing. 219 */ 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