src/cpu/ozone/inst_queue.hh

   1 /*
   2  * Copyright (c) 2004-2006 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Kevin Lim
  29  */
  30
  31 #ifndef __CPU_OZONE_INST_QUEUE_HH__
  32 #define __CPU_OZONE_INST_QUEUE_HH__
  33
  34 #include <list>
  35 #include <map>
  36 #include <queue>
  37 #include <vector>
  38
  39 #include "base/statistics.hh"
  40 #include "base/timebuf.hh"
  41 #include "cpu/inst_seq.hh"
  42 #include "base/types.hh"
  43
  44 class FUPool;
  45 class MemInterface;
  46
  47 /**
  48  * A standard instruction queue class.  It holds ready instructions, in
  49  * order, in seperate priority queues to facilitate the scheduling of
  50  * instructions.  The IQ uses a separate linked list to track dependencies.
  51  * Similar to the rename map and the free list, it expects that
  52  * floating point registers have their indices start after the integer
  53  * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
  54  * and 96-191 are fp).  This remains true even for both logical and
  55  * physical register indices. The IQ depends on the memory dependence unit to
  56  * track when memory operations are ready in terms of ordering; register
  57  * dependencies are tracked normally. Right now the IQ also handles the
  58  * execution timing; this is mainly to allow back-to-back scheduling without
  59  * requiring IEW to be able to peek into the IQ. At the end of the execution
  60  * latency, the instruction is put into the queue to execute, where it will
  61  * have the execute() function called on it.
  62  * @todo: Make IQ able to handle multiple FU pools.
  63  */
  64 template <class Impl>
  65 class InstQueue
  66 {
  67   public:
  68     //Typedefs from the Impl.
  69     typedef typename Impl::FullCPU FullCPU;
  70     typedef typename Impl::DynInstPtr DynInstPtr;
  71     typedef typename Impl::Params Params;
  72     typedef typename Impl::IssueStruct IssueStruct;
  73 /*
  74     typedef typename Impl::CPUPol::IEW IEW;
  75     typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
  76     typedef typename Impl::CPUPol::IssueStruct IssueStruct;
  77     typedef typename Impl::CPUPol::TimeStruct TimeStruct;
  78 */
  79     // Typedef of iterator through the list of instructions.
  80     typedef typename std::list<DynInstPtr>::iterator ListIt;
  81
  82     friend class Impl::FullCPU;
  83 #if 0
  84     /** FU completion event class. */
  85     class FUCompletion : public Event {
  86       private:
  87         /** Executing instruction. */
  88         DynInstPtr inst;
  89
  90         /** Index of the FU used for executing. */
  91         int fuIdx;
  92
  93         /** Pointer back to the instruction queue. */
  94         InstQueue<Impl> *iqPtr;
  95
  96       public:
  97         /** Construct a FU completion event. */
  98         FUCompletion(DynInstPtr &_inst, int fu_idx,
  99                      InstQueue<Impl> *iq_ptr);
 100
 101         virtual void process();
 102         virtual const char *description() const;
 103     };
 104 #endif
 105     /** Constructs an IQ. */
 106     InstQueue(Params *params);
 107
 108     /** Destructs the IQ. */
 109     ~InstQueue();
 110
 111     /** Returns the name of the IQ. */
 112     std::string name() const;
 113
 114     /** Registers statistics. */
 115     void regStats();
 116
 117     /** Sets CPU pointer. */
 118     void setCPU(FullCPU *_cpu) { cpu = _cpu; }
 119 #if 0
 120     /** Sets active threads list. */
 121     void setActiveThreads(list<unsigned> *at_ptr);
 122
 123     /** Sets the IEW pointer. */
 124     void setIEW(IEW *iew_ptr) { iewStage = iew_ptr; }
 125 #endif
 126     /** Sets the timer buffer between issue and execute. */
 127     void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
 128 #if 0
 129     /** Sets the global time buffer. */
 130     void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
 131
 132     /** Number of entries needed for given amount of threads. */
 133     int entryAmount(int num_threads);
 134
 135     /** Resets max entries for all threads. */
 136     void resetEntries();
 137 #endif
 138     /** Returns total number of free entries. */
 139     unsigned numFreeEntries();
 140
 141     /** Returns number of free entries for a thread. */
 142     unsigned numFreeEntries(unsigned tid);
 143
 144     /** Returns whether or not the IQ is full. */
 145     bool isFull();
 146
 147     /** Returns whether or not the IQ is full for a specific thread. */
 148     bool isFull(unsigned tid);
 149
 150     /** Returns if there are any ready instructions in the IQ. */
 151     bool hasReadyInsts();
 152
 153     /** Inserts a new instruction into the IQ. */
 154     void insert(DynInstPtr &new_inst);
 155
 156     /** Inserts a new, non-speculative instruction into the IQ. */
 157     void insertNonSpec(DynInstPtr &new_inst);
 158 #if 0
 159     /**
 160      * Advances the tail of the IQ, used if an instruction is not added to the
 161      * IQ for scheduling.
 162      * @todo: Rename this function.
 163      */
 164     void advanceTail(DynInstPtr &inst);
 165
 166     /** Process FU completion event. */
 167     void processFUCompletion(DynInstPtr &inst, int fu_idx);
 168 #endif
 169     /**
 170      * Schedules ready instructions, adding the ready ones (oldest first) to
 171      * the queue to execute.
 172      */
 173     void scheduleReadyInsts();
 174
 175     /** Schedules a single specific non-speculative instruction. */
 176     void scheduleNonSpec(const InstSeqNum &inst);
 177
 178     /**
 179      * Commits all instructions up to and including the given sequence number,
 180      * for a specific thread.
 181      */
 182     void commit(const InstSeqNum &inst, unsigned tid = 0);
 183
 184     /** Wakes all dependents of a completed instruction. */
 185     void wakeDependents(DynInstPtr &completed_inst);
 186
 187     /** Adds a ready memory instruction to the ready list. */
 188     void addReadyMemInst(DynInstPtr &ready_inst);
 189 #if 0
 190     /**
 191      * Reschedules a memory instruction. It will be ready to issue once
 192      * replayMemInst() is called.
 193      */
 194     void rescheduleMemInst(DynInstPtr &resched_inst);
 195
 196     /** Replays a memory instruction. It must be rescheduled first. */
 197     void replayMemInst(DynInstPtr &replay_inst);
 198 #endif
 199     /** Completes a memory operation. */
 200     void completeMemInst(DynInstPtr &completed_inst);
 201 #if 0
 202     /** Indicates an ordering violation between a store and a load. */
 203     void violation(DynInstPtr &store, DynInstPtr &faulting_load);
 204 #endif
 205     /**
 206      * Squashes instructions for a thread. Squashing information is obtained
 207      * from the time buffer.
 208      */
 209     void squash(unsigned tid); // Probably want the ISN
 210
 211     /** Returns the number of used entries for a thread. */
 212     unsigned getCount(unsigned tid) { return count[tid]; };
 213
 214     /** Updates the number of free entries. */
 215     void updateFreeEntries(int num) { freeEntries += num; }
 216
 217     /** Debug function to print all instructions. */
 218     void printInsts();
 219
 220   private:
 221     /** Does the actual squashing. */
 222     void doSquash(unsigned tid);
 223
 224     /////////////////////////
 225     // Various pointers
 226     /////////////////////////
 227
 228     /** Pointer to the CPU. */
 229     FullCPU *cpu;
 230
 231     /** Cache interface. */
 232     MemInterface *dcacheInterface;
 233 #if 0
 234     /** Pointer to IEW stage. */
 235     IEW *iewStage;
 236
 237     /** The memory dependence unit, which tracks/predicts memory dependences
 238      *  between instructions.
 239      */
 240     MemDepUnit memDepUnit[Impl::MaxThreads];
 241 #endif
 242     /** The queue to the execute stage.  Issued instructions will be written
 243      *  into it.
 244      */
 245     TimeBuffer<IssueStruct> *issueToExecuteQueue;
 246 #if 0
 247     /** The backwards time buffer. */
 248     TimeBuffer<TimeStruct> *timeBuffer;
 249
 250     /** Wire to read information from timebuffer. */
 251     typename TimeBuffer<TimeStruct>::wire fromCommit;
 252
 253     /** Function unit pool. */
 254     FUPool *fuPool;
 255 #endif
 256     //////////////////////////////////////
 257     // Instruction lists, ready queues, and ordering
 258     //////////////////////////////////////
 259
 260     /** List of all the instructions in the IQ (some of which may be issued). */
 261     std::list<DynInstPtr> instList[Impl::MaxThreads];
 262
 263     /**
 264      * Struct for comparing entries to be added to the priority queue.  This
 265      * gives reverse ordering to the instructions in terms of sequence
 266      * numbers: the instructions with smaller sequence numbers (and hence
 267      * are older) will be at the top of the priority queue.
 268      */
 269     struct pqCompare {
 270         bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
 271         {
 272             return lhs->seqNum > rhs->seqNum;
 273         }
 274     };
 275
 276     /**
 277      * Struct for an IQ entry. It includes the instruction and an iterator
 278      * to the instruction's spot in the IQ.
 279      */
 280     struct IQEntry {
 281         DynInstPtr inst;
 282         ListIt iqIt;
 283     };
 284
 285     typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
 286     ReadyInstQueue;
 287
 288     typedef std::map<DynInstPtr, pqCompare> ReadyInstMap;
 289     typedef typename std::map<DynInstPtr, pqCompare>::iterator ReadyMapIt;
 290
 291     /** List of ready instructions.
 292      */
 293     ReadyInstQueue readyInsts;
 294
 295     /** List of non-speculative instructions that will be scheduled
 296      *  once the IQ gets a signal from commit.  While it's redundant to
 297      *  have the key be a part of the value (the sequence number is stored
 298      *  inside of DynInst), when these instructions are woken up only
 299      *  the sequence number will be available.  Thus it is most efficient to be
 300      *  able to search by the sequence number alone.
 301      */
 302     std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
 303
 304     typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;
 305 #if 0
 306     /** Entry for the list age ordering by op class. */
 307     struct ListOrderEntry {
 308         OpClass queueType;
 309         InstSeqNum oldestInst;
 310     };
 311
 312     /** List that contains the age order of the oldest instruction of each
 313      *  ready queue.  Used to select the oldest instruction available
 314      *  among op classes.
 315      */
 316     std::list<ListOrderEntry> listOrder;
 317
 318     typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;
 319
 320     /** Tracks if each ready queue is on the age order list. */
 321     bool queueOnList[Num_OpClasses];
 322
 323     /** Iterators of each ready queue.  Points to their spot in the age order
 324      *  list.
 325      */
 326     ListOrderIt readyIt[Num_OpClasses];
 327
 328     /** Add an op class to the age order list. */
 329     void addToOrderList(OpClass op_class);
 330
 331     /**
 332      * Called when the oldest instruction has been removed from a ready queue;
 333      * this places that ready queue into the proper spot in the age order list.
 334      */
 335     void moveToYoungerInst(ListOrderIt age_order_it);
 336 #endif
 337     //////////////////////////////////////
 338     // Various parameters
 339     //////////////////////////////////////
 340 #if 0
 341     /** IQ Resource Sharing Policy */
 342     enum IQPolicy {
 343         Dynamic,
 344         Partitioned,
 345         Threshold
 346     };
 347
 348     /** IQ sharing policy for SMT. */
 349     IQPolicy iqPolicy;
 350 #endif
 351     /** Number of Total Threads*/
 352     unsigned numThreads;
 353 #if 0
 354     /** Pointer to list of active threads. */
 355     list<unsigned> *activeThreads;
 356 #endif
 357     /** Per Thread IQ count */
 358     unsigned count[Impl::MaxThreads];
 359
 360     /** Max IQ Entries Per Thread */
 361     unsigned maxEntries[Impl::MaxThreads];
 362
 363     /** Number of free IQ entries left. */
 364     unsigned freeEntries;
 365
 366     /** The number of entries in the instruction queue. */
 367     unsigned numEntries;
 368
 369     /** The total number of instructions that can be issued in one cycle. */
 370     unsigned totalWidth;
 371 #if 0
 372     /** The number of physical registers in the CPU. */
 373     unsigned numPhysRegs;
 374
 375     /** The number of physical integer registers in the CPU. */
 376     unsigned numPhysIntRegs;
 377
 378     /** The number of floating point registers in the CPU. */
 379     unsigned numPhysFloatRegs;
 380 #endif
 381     /** Delay between commit stage and the IQ.
 382      *  @todo: Make there be a distinction between the delays within IEW.
 383      */
 384     unsigned commitToIEWDelay;
 385
 386     //////////////////////////////////
 387     // Variables needed for squashing
 388     //////////////////////////////////
 389
 390     /** The sequence number of the squashed instruction. */
 391     InstSeqNum squashedSeqNum[Impl::MaxThreads];
 392
 393     /** Iterator that points to the last instruction that has been squashed.
 394      *  This will not be valid unless the IQ is in the process of squashing.
 395      */
 396     ListIt squashIt[Impl::MaxThreads];
 397 #if 0
 398     ///////////////////////////////////
 399     // Dependency graph stuff
 400     ///////////////////////////////////
 401
 402     class DependencyEntry
 403     {
 404       public:
 405         DependencyEntry()
 406             : inst(NULL), next(NULL)
 407         { }
 408
 409         DynInstPtr inst;
 410         //Might want to include data about what arch. register the
 411         //dependence is waiting on.
 412         DependencyEntry *next;
 413
 414         //This function, and perhaps this whole class, stand out a little
 415         //bit as they don't fit a classification well.  I want access
 416         //to the underlying structure of the linked list, yet at
 417         //the same time it feels like this should be something abstracted
 418         //away.  So for now it will sit here, within the IQ, until
 419         //a better implementation is decided upon.
 420         // This function probably shouldn't be within the entry...
 421         void insert(DynInstPtr &new_inst);
 422
 423         void remove(DynInstPtr &inst_to_remove);
 424
 425         // Debug variable, remove when done testing.
 426         static unsigned mem_alloc_counter;
 427     };
 428
 429     /** Array of linked lists.  Each linked list is a list of all the
 430      *  instructions that depend upon a given register.  The actual
 431      *  register's index is used to index into the graph; ie all
 432      *  instructions in flight that are dependent upon r34 will be
 433      *  in the linked list of dependGraph[34].
 434      */
 435     DependencyEntry *dependGraph;
 436
 437     /** A cache of the recently woken registers.  It is 1 if the register
 438      *  has been woken up recently, and 0 if the register has been added
 439      *  to the dependency graph and has not yet received its value.  It
 440      *  is basically a secondary scoreboard, and should pretty much mirror
 441      *  the scoreboard that exists in the rename map.
 442      */
 443     vector<bool> regScoreboard;
 444
 445     /** Adds an instruction to the dependency graph, as a producer. */
 446     bool addToDependents(DynInstPtr &new_inst);
 447
 448     /** Adds an instruction to the dependency graph, as a consumer. */
 449     void createDependency(DynInstPtr &new_inst);
 450 #endif
 451     /** Moves an instruction to the ready queue if it is ready. */
 452     void addIfReady(DynInstPtr &inst);
 453
 454     /** Debugging function to count how many entries are in the IQ.  It does
 455      *  a linear walk through the instructions, so do not call this function
 456      *  during normal execution.
 457      */
 458     int countInsts();
 459 #if 0
 460     /** Debugging function to dump out the dependency graph.
 461      */
 462     void dumpDependGraph();
 463 #endif
 464     /** Debugging function to dump all the list sizes, as well as print
 465      *  out the list of nonspeculative instructions.  Should not be used
 466      *  in any other capacity, but it has no harmful sideaffects.
 467      */
 468     void dumpLists();
 469
 470     /** Debugging function to dump out all instructions that are in the
 471      *  IQ.
 472      */
 473     void dumpInsts();
 474
 475     /** Stat for number of instructions added. */
 476     Stats::Scalar iqInstsAdded;
 477     /** Stat for number of non-speculative instructions added. */
 478     Stats::Scalar iqNonSpecInstsAdded;
 479 //    Stats::Scalar iqIntInstsAdded;
 480     /** Stat for number of integer instructions issued. */
 481     Stats::Scalar iqIntInstsIssued;
 482 //    Stats::Scalar iqFloatInstsAdded;
 483     /** Stat for number of floating point instructions issued. */
 484     Stats::Scalar iqFloatInstsIssued;
 485 //    Stats::Scalar iqBranchInstsAdded;
 486     /** Stat for number of branch instructions issued. */
 487     Stats::Scalar iqBranchInstsIssued;
 488 //    Stats::Scalar iqMemInstsAdded;
 489     /** Stat for number of memory instructions issued. */
 490     Stats::Scalar iqMemInstsIssued;
 491 //    Stats::Scalar iqMiscInstsAdded;
 492     /** Stat for number of miscellaneous instructions issued. */
 493     Stats::Scalar iqMiscInstsIssued;
 494     /** Stat for number of squashed instructions that were ready to issue. */
 495     Stats::Scalar iqSquashedInstsIssued;
 496     /** Stat for number of squashed instructions examined when squashing. */
 497     Stats::Scalar iqSquashedInstsExamined;
 498     /** Stat for number of squashed instruction operands examined when
 499      * squashing.
 500      */
 501     Stats::Scalar iqSquashedOperandsExamined;
 502     /** Stat for number of non-speculative instructions removed due to a squash.
 503      */
 504     Stats::Scalar iqSquashedNonSpecRemoved;
 505
 506 };
 507
 508 #endif //__CPU_OZONE_INST_QUEUE_HH__