inst_queue.hh revision 1681
12SN/A#ifndef __INST_QUEUE_HH__ 21762SN/A#define __INST_QUEUE_HH__ 32SN/A 42SN/A#include <list> 52SN/A#include <map> 62SN/A#include <queue> 72SN/A#include <stdint.h> 82SN/A#include <vector> 92SN/A 102SN/A#include "base/statistics.hh" 112SN/A#include "base/timebuf.hh" 122SN/A#include "cpu/inst_seq.hh" 132SN/A 142SN/A/** 152SN/A * A standard instruction queue class. It holds instructions in an 162SN/A * array, holds the ordering of the instructions within a linked list, 172SN/A * and tracks producer/consumer dependencies within a separate linked 182SN/A * list. Similar to the rename map and the free list, it expects that 192SN/A * floating point registers have their indices start after the integer 202SN/A * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer 212SN/A * and 96-191 are fp). This remains true even for both logical and 222SN/A * physical register indices. 232SN/A */ 242SN/Atemplate <class Impl> 252SN/Aclass InstructionQueue 262SN/A{ 272665Ssaidi@eecs.umich.edu public: 282665Ssaidi@eecs.umich.edu //Typedefs from the Impl. 292665Ssaidi@eecs.umich.edu typedef typename Impl::FullCPU FullCPU; 302SN/A typedef typename Impl::DynInstPtr DynInstPtr; 312SN/A typedef typename Impl::Params Params; 324183Sgblack@eecs.umich.edu 332439SN/A typedef typename Impl::CPUPol::MemDepUnit MemDepUnit; 342680Sktlim@umich.edu typedef typename Impl::CPUPol::IssueStruct IssueStruct; 352222SN/A typedef typename Impl::CPUPol::TimeStruct TimeStruct; 364183Sgblack@eecs.umich.edu 374183Sgblack@eecs.umich.edu // Typedef of iterator through the list of instructions. Might be 384183Sgblack@eecs.umich.edu // better to untie this from the FullCPU or pass its information to 392SN/A // the stages. 402201SN/A typedef typename std::list<DynInstPtr>::iterator ListIt; 417678Sgblack@eecs.umich.edu 422201SN/A /** 436815SLisa.Hsu@amd.com * Struct for comparing entries to be added to the priority queue. This 442201SN/A * gives reverse ordering to the instructions in terms of sequence 452222SN/A * numbers: the instructions with smaller sequence numbers (and hence 467678Sgblack@eecs.umich.edu * are older) will be at the top of the priority queue. 472222SN/A */ 482680Sktlim@umich.edu struct pqCompare 492222SN/A { 502680Sktlim@umich.edu bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 512222SN/A { 522201SN/A return lhs->seqNum > rhs->seqNum; 532612SN/A } 547678Sgblack@eecs.umich.edu }; 552612SN/A 566815SLisa.Hsu@amd.com /** 572612SN/A * Struct for comparing entries to be added to the set. This gives 585004Sgblack@eecs.umich.edu * standard ordering in terms of sequence numbers. 594184Ssaidi@eecs.umich.edu */ 607678Sgblack@eecs.umich.edu struct setCompare 614183Sgblack@eecs.umich.edu { 624183Sgblack@eecs.umich.edu bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const 634183Sgblack@eecs.umich.edu { 644434Ssaidi@eecs.umich.edu return lhs->seqNum < rhs->seqNum; 654183Sgblack@eecs.umich.edu } 664434Ssaidi@eecs.umich.edu }; 674183Sgblack@eecs.umich.edu 685004Sgblack@eecs.umich.edu typedef std::priority_queue<DynInstPtr, vector<DynInstPtr>, pqCompare> 697678Sgblack@eecs.umich.edu ReadyInstQueue; 705004Sgblack@eecs.umich.edu 715004Sgblack@eecs.umich.edu InstructionQueue(Params ¶ms); 725004Sgblack@eecs.umich.edu 734184Ssaidi@eecs.umich.edu void regStats(); 74 75 void setCPU(FullCPU *cpu); 76 77 void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue); 78 79 void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr); 80 81 unsigned numFreeEntries(); 82 83 bool isFull(); 84 85 void insert(DynInstPtr &new_inst); 86 87 void insertNonSpec(DynInstPtr &new_inst); 88 89 void advanceTail(DynInstPtr &inst); 90 91 void scheduleReadyInsts(); 92 93 void scheduleNonSpec(const InstSeqNum &inst); 94 95 void wakeDependents(DynInstPtr &completed_inst); 96 97 void violation(DynInstPtr &store, DynInstPtr &faulting_load); 98 99 // Change this to take in the sequence number 100 void squash(); 101 102 void doSquash(); 103 104 void stopSquash(); 105 106 /** Debugging function to dump all the list sizes, as well as print 107 * out the list of nonspeculative instructions. Should not be used 108 * in any other capacity, but it has no harmful sideaffects. 109 */ 110 void dumpLists(); 111 112 private: 113 /** Debugging function to count how many entries are in the IQ. It does 114 * a linear walk through the instructions, so do not call this function 115 * during normal execution. 116 */ 117 int countInsts(); 118 119 private: 120 /** Pointer to the CPU. */ 121 FullCPU *cpu; 122 123 /** The memory dependence unit, which tracks/predicts memory dependences 124 * between instructions. 125 */ 126 MemDepUnit memDepUnit; 127 128 /** The queue to the execute stage. Issued instructions will be written 129 * into it. 130 */ 131 TimeBuffer<IssueStruct> *issueToExecuteQueue; 132 133 /** The backwards time buffer. */ 134 TimeBuffer<TimeStruct> *timeBuffer; 135 136 /** Wire to read information from timebuffer. */ 137 typename TimeBuffer<TimeStruct>::wire fromCommit; 138 139 enum InstList { 140 Int, 141 Float, 142 Branch, 143 Memory, 144 Misc, 145 Squashed, 146 None 147 }; 148 149 /** List of ready int instructions. Used to keep track of the order in 150 * which instructions should issue. 151 */ 152 ReadyInstQueue readyIntInsts; 153 154 /** List of ready floating point instructions. */ 155 ReadyInstQueue readyFloatInsts; 156 157 /** List of ready branch instructions. */ 158 ReadyInstQueue readyBranchInsts; 159 160 /** List of ready memory instructions. */ 161// ReadyInstQueue readyMemInsts; 162 163 /** List of ready miscellaneous instructions. */ 164 ReadyInstQueue readyMiscInsts; 165 166 /** List of squashed instructions (which are still valid and in IQ). 167 * Implemented using a priority queue; the entries must contain both 168 * the IQ index and sequence number of each instruction so that 169 * ordering based on sequence numbers can be used. 170 */ 171 ReadyInstQueue squashedInsts; 172 173 /** List of non-speculative instructions that will be scheduled 174 * once the IQ gets a signal from commit. While it's redundant to 175 * have the key be a part of the value (the sequence number is stored 176 * inside of DynInst), when these instructions are woken up only 177 * the sequence number will be available. Thus it is most efficient to be 178 * able to search by the sequence number alone. 179 */ 180 std::map<InstSeqNum, DynInstPtr> nonSpecInsts; 181 182 typedef typename std::map<InstSeqNum, DynInstPtr>::iterator non_spec_it_t; 183 184 /** Number of free IQ entries left. */ 185 unsigned freeEntries; 186 187 /** The number of entries in the instruction queue. */ 188 unsigned numEntries; 189 190 /** The number of integer instructions that can be issued in one 191 * cycle. 192 */ 193 unsigned intWidth; 194 195 /** The number of floating point instructions that can be issued 196 * in one cycle. 197 */ 198 unsigned floatWidth; 199 200 /** The number of branches that can be issued in one cycle. */ 201 unsigned branchWidth; 202 203 /** The number of memory instructions that can be issued in one cycle. */ 204 unsigned memoryWidth; 205 206 /** The total number of instructions that can be issued in one cycle. */ 207 unsigned totalWidth; 208 209 //The number of physical registers in the CPU. 210 unsigned numPhysRegs; 211 212 /** The number of physical integer registers in the CPU. */ 213 unsigned numPhysIntRegs; 214 215 /** The number of floating point registers in the CPU. */ 216 unsigned numPhysFloatRegs; 217 218 /** Delay between commit stage and the IQ. 219 * @todo: Make there be a distinction between the delays within IEW. 220 */ 221 unsigned commitToIEWDelay; 222 223 ////////////////////////////////// 224 // Variables needed for squashing 225 ////////////////////////////////// 226 227 /** The sequence number of the squashed instruction. */ 228 InstSeqNum squashedSeqNum; 229 230 /** Iterator that points to the youngest instruction in the IQ. */ 231 ListIt tail; 232 233 /** Iterator that points to the last instruction that has been squashed. 234 * This will not be valid unless the IQ is in the process of squashing. 235 */ 236 ListIt squashIt; 237 238 /////////////////////////////////// 239 // Dependency graph stuff 240 /////////////////////////////////// 241 242 class DependencyEntry 243 { 244 public: 245 DynInstPtr inst; 246 //Might want to include data about what arch. register the 247 //dependence is waiting on. 248 DependencyEntry *next; 249 250 //This function, and perhaps this whole class, stand out a little 251 //bit as they don't fit a classification well. I want access 252 //to the underlying structure of the linked list, yet at 253 //the same time it feels like this should be something abstracted 254 //away. So for now it will sit here, within the IQ, until 255 //a better implementation is decided upon. 256 // This function probably shouldn't be within the entry... 257 void insert(DynInstPtr &new_inst); 258 259 void remove(DynInstPtr &inst_to_remove); 260 261 // Debug variable, remove when done testing. 262 static unsigned mem_alloc_counter; 263 }; 264 265 /** Array of linked lists. Each linked list is a list of all the 266 * instructions that depend upon a given register. The actual 267 * register's index is used to index into the graph; ie all 268 * instructions in flight that are dependent upon r34 will be 269 * in the linked list of dependGraph[34]. 270 */ 271 DependencyEntry *dependGraph; 272 273 /** A cache of the recently woken registers. It is 1 if the register 274 * has been woken up recently, and 0 if the register has been added 275 * to the dependency graph and has not yet received its value. It 276 * is basically a secondary scoreboard, and should pretty much mirror 277 * the scoreboard that exists in the rename map. 278 */ 279 vector<bool> regScoreboard; 280 281 bool addToDependents(DynInstPtr &new_inst); 282 void insertDependency(DynInstPtr &new_inst); 283 void createDependency(DynInstPtr &new_inst); 284 void dumpDependGraph(); 285 286 void addIfReady(DynInstPtr &inst); 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 //__INST_QUEUE_HH__ 309