src/cpu/o3/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_O3_INST_QUEUE_HH__
  32 #define __CPU_O3_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 "cpu/o3/dep_graph.hh"
  43 #include "cpu/op_class.hh"
  44 #include "sim/host.hh"
  45
  46 class FUPool;
  47 class MemInterface;
  48
  49 /**
  50  * A standard instruction queue class.  It holds ready instructions, in
  51  * order, in seperate priority queues to facilitate the scheduling of
  52  * instructions.  The IQ uses a separate linked list to track dependencies.
  53  * Similar to the rename map and the free list, it expects that
  54  * floating point registers have their indices start after the integer
  55  * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
  56  * and 96-191 are fp).  This remains true even for both logical and
  57  * physical register indices. The IQ depends on the memory dependence unit to
  58  * track when memory operations are ready in terms of ordering; register
  59  * dependencies are tracked normally. Right now the IQ also handles the
  60  * execution timing; this is mainly to allow back-to-back scheduling without
  61  * requiring IEW to be able to peek into the IQ. At the end of the execution
  62  * latency, the instruction is put into the queue to execute, where it will
  63  * have the execute() function called on it.
  64  * @todo: Make IQ able to handle multiple FU pools.
  65  */
  66 template <class Impl>
  67 class InstructionQueue
  68 {
  69   public:
  70     //Typedefs from the Impl.
  71     typedef typename Impl::O3CPU O3CPU;
  72     typedef typename Impl::DynInstPtr DynInstPtr;
  73     typedef typename Impl::Params Params;
  74
  75     typedef typename Impl::CPUPol::IEW IEW;
  76     typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
  77     typedef typename Impl::CPUPol::IssueStruct IssueStruct;
  78     typedef typename Impl::CPUPol::TimeStruct TimeStruct;
  79
  80     // Typedef of iterator through the list of instructions.
  81     typedef typename std::list<DynInstPtr>::iterator ListIt;
  82
  83     friend class Impl::O3CPU;
  84
  85     /** FU completion event class. */
  86     class FUCompletion : public Event {
  87       private:
  88         /** Executing instruction. */
  89         DynInstPtr inst;
  90
  91         /** Index of the FU used for executing. */
  92         int fuIdx;
  93
  94         /** Pointer back to the instruction queue. */
  95         InstructionQueue<Impl> *iqPtr;
  96
  97         /** Should the FU be added to the list to be freed upon
  98          * completing this event.
  99          */
 100         bool freeFU;
 101
 102       public:
 103         /** Construct a FU completion event. */
 104         FUCompletion(DynInstPtr &_inst, int fu_idx,
 105                      InstructionQueue<Impl> *iq_ptr);
 106
 107         virtual void process();
 108         virtual const char *description();
 109         void setFreeFU() { freeFU = true; }
 110     };
 111
 112     /** Constructs an IQ. */
 113     InstructionQueue(Params *params);
 114
 115     /** Destructs the IQ. */
 116     ~InstructionQueue();
 117
 118     /** Returns the name of the IQ. */
 119     std::string name() const;
 120
 121     /** Registers statistics. */
 122     void regStats();
 123
 124     /** Resets all instruction queue state. */
 125     void resetState();
 126
 127     /** Sets CPU pointer. */
 128     void setCPU(O3CPU *_cpu) { cpu = _cpu; }
 129
 130     /** Sets active threads list. */
 131     void setActiveThreads(std::list<unsigned> *at_ptr);
 132
 133     /** Sets the IEW pointer. */
 134     void setIEW(IEW *iew_ptr) { iewStage = iew_ptr; }
 135
 136     /** Sets the timer buffer between issue and execute. */
 137     void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);
 138
 139     /** Sets the global time buffer. */
 140     void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);
 141
 142     /** Switches out the instruction queue. */
 143     void switchOut();
 144
 145     /** Takes over execution from another CPU's thread. */
 146     void takeOverFrom();
 147
 148     /** Returns if the IQ is switched out. */
 149     bool isSwitchedOut() { return switchedOut; }
 150
 151     /** Number of entries needed for given amount of threads. */
 152     int entryAmount(int num_threads);
 153
 154     /** Resets max entries for all threads. */
 155     void resetEntries();
 156
 157     /** Returns total number of free entries. */
 158     unsigned numFreeEntries();
 159
 160     /** Returns number of free entries for a thread. */
 161     unsigned numFreeEntries(unsigned tid);
 162
 163     /** Returns whether or not the IQ is full. */
 164     bool isFull();
 165
 166     /** Returns whether or not the IQ is full for a specific thread. */
 167     bool isFull(unsigned tid);
 168
 169     /** Returns if there are any ready instructions in the IQ. */
 170     bool hasReadyInsts();
 171
 172     /** Inserts a new instruction into the IQ. */
 173     void insert(DynInstPtr &new_inst);
 174
 175     /** Inserts a new, non-speculative instruction into the IQ. */
 176     void insertNonSpec(DynInstPtr &new_inst);
 177
 178     /** Inserts a memory or write barrier into the IQ to make sure
 179      *  loads and stores are ordered properly.
 180      */
 181     void insertBarrier(DynInstPtr &barr_inst);
 182
 183     /** Returns the oldest scheduled instruction, and removes it from
 184      * the list of instructions waiting to execute.
 185      */
 186     DynInstPtr getInstToExecute();
 187
 188     /**
 189      * Records the instruction as the producer of a register without
 190      * adding it to the rest of the IQ.
 191      */
 192     void recordProducer(DynInstPtr &inst)
 193     { addToProducers(inst); }
 194
 195     /** Process FU completion event. */
 196     void processFUCompletion(DynInstPtr &inst, int fu_idx);
 197
 198     /**
 199      * Schedules ready instructions, adding the ready ones (oldest first) to
 200      * the queue to execute.
 201      */
 202     void scheduleReadyInsts();
 203
 204     /** Schedules a single specific non-speculative instruction. */
 205     void scheduleNonSpec(const InstSeqNum &inst);
 206
 207     /**
 208      * Commits all instructions up to and including the given sequence number,
 209      * for a specific thread.
 210      */
 211     void commit(const InstSeqNum &inst, unsigned tid = 0);
 212
 213     /** Wakes all dependents of a completed instruction. */
 214     int wakeDependents(DynInstPtr &completed_inst);
 215
 216     /** Adds a ready memory instruction to the ready list. */
 217     void addReadyMemInst(DynInstPtr &ready_inst);
 218
 219     /**
 220      * Reschedules a memory instruction. It will be ready to issue once
 221      * replayMemInst() is called.
 222      */
 223     void rescheduleMemInst(DynInstPtr &resched_inst);
 224
 225     /** Replays a memory instruction. It must be rescheduled first. */
 226     void replayMemInst(DynInstPtr &replay_inst);
 227
 228     /** Completes a memory operation. */
 229     void completeMemInst(DynInstPtr &completed_inst);
 230
 231     /** Indicates an ordering violation between a store and a load. */
 232     void violation(DynInstPtr &store, DynInstPtr &faulting_load);
 233
 234     /**
 235      * Squashes instructions for a thread. Squashing information is obtained
 236      * from the time buffer.
 237      */
 238     void squash(unsigned tid);
 239
 240     /** Returns the number of used entries for a thread. */
 241     unsigned getCount(unsigned tid) { return count[tid]; };
 242
 243     /** Debug function to print all instructions. */
 244     void printInsts();
 245
 246   private:
 247     /** Does the actual squashing. */
 248     void doSquash(unsigned tid);
 249
 250     /////////////////////////
 251     // Various pointers
 252     /////////////////////////
 253
 254     /** Pointer to the CPU. */
 255     O3CPU *cpu;
 256
 257     /** Cache interface. */
 258     MemInterface *dcacheInterface;
 259
 260     /** Pointer to IEW stage. */
 261     IEW *iewStage;
 262
 263     /** The memory dependence unit, which tracks/predicts memory dependences
 264      *  between instructions.
 265      */
 266     MemDepUnit memDepUnit[Impl::MaxThreads];
 267
 268     /** The queue to the execute stage.  Issued instructions will be written
 269      *  into it.
 270      */
 271     TimeBuffer<IssueStruct> *issueToExecuteQueue;
 272
 273     /** The backwards time buffer. */
 274     TimeBuffer<TimeStruct> *timeBuffer;
 275
 276     /** Wire to read information from timebuffer. */
 277     typename TimeBuffer<TimeStruct>::wire fromCommit;
 278
 279     /** Function unit pool. */
 280     FUPool *fuPool;
 281
 282     //////////////////////////////////////
 283     // Instruction lists, ready queues, and ordering
 284     //////////////////////////////////////
 285
 286     /** List of all the instructions in the IQ (some of which may be issued). */
 287     std::list<DynInstPtr> instList[Impl::MaxThreads];
 288
 289     /** List of instructions that are ready to be executed. */
 290     std::list<DynInstPtr> instsToExecute;
 291
 292     /**
 293      * Struct for comparing entries to be added to the priority queue.
 294      * This gives reverse ordering to the instructions in terms of
 295      * sequence numbers: the instructions with smaller sequence
 296      * numbers (and hence are older) will be at the top of the
 297      * priority queue.
 298      */
 299     struct pqCompare {
 300         bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
 301         {
 302             return lhs->seqNum > rhs->seqNum;
 303         }
 304     };
 305
 306     typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
 307     ReadyInstQueue;
 308
 309     /** List of ready instructions, per op class.  They are separated by op
 310      *  class to allow for easy mapping to FUs.
 311      */
 312     ReadyInstQueue readyInsts[Num_OpClasses];
 313
 314     /** List of non-speculative instructions that will be scheduled
 315      *  once the IQ gets a signal from commit.  While it's redundant to
 316      *  have the key be a part of the value (the sequence number is stored
 317      *  inside of DynInst), when these instructions are woken up only
 318      *  the sequence number will be available.  Thus it is most efficient to be
 319      *  able to search by the sequence number alone.
 320      */
 321     std::map<InstSeqNum, DynInstPtr> nonSpecInsts;
 322
 323     typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;
 324
 325     /** Entry for the list age ordering by op class. */
 326     struct ListOrderEntry {
 327         OpClass queueType;
 328         InstSeqNum oldestInst;
 329     };
 330
 331     /** List that contains the age order of the oldest instruction of each
 332      *  ready queue.  Used to select the oldest instruction available
 333      *  among op classes.
 334      *  @todo: Might be better to just move these entries around instead
 335      *  of creating new ones every time the position changes due to an
 336      *  instruction issuing.  Not sure std::list supports this.
 337      */
 338     std::list<ListOrderEntry> listOrder;
 339
 340     typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;
 341
 342     /** Tracks if each ready queue is on the age order list. */
 343     bool queueOnList[Num_OpClasses];
 344
 345     /** Iterators of each ready queue.  Points to their spot in the age order
 346      *  list.
 347      */
 348     ListOrderIt readyIt[Num_OpClasses];
 349
 350     /** Add an op class to the age order list. */
 351     void addToOrderList(OpClass op_class);
 352
 353     /**
 354      * Called when the oldest instruction has been removed from a ready queue;
 355      * this places that ready queue into the proper spot in the age order list.
 356      */
 357     void moveToYoungerInst(ListOrderIt age_order_it);
 358
 359     DependencyGraph<DynInstPtr> dependGraph;
 360
 361     //////////////////////////////////////
 362     // Various parameters
 363     //////////////////////////////////////
 364
 365     /** IQ Resource Sharing Policy */
 366     enum IQPolicy {
 367         Dynamic,
 368         Partitioned,
 369         Threshold
 370     };
 371
 372     /** IQ sharing policy for SMT. */
 373     IQPolicy iqPolicy;
 374
 375     /** Number of Total Threads*/
 376     unsigned numThreads;
 377
 378     /** Pointer to list of active threads. */
 379     std::list<unsigned> *activeThreads;
 380
 381     /** Per Thread IQ count */
 382     unsigned count[Impl::MaxThreads];
 383
 384     /** Max IQ Entries Per Thread */
 385     unsigned maxEntries[Impl::MaxThreads];
 386
 387     /** Number of free IQ entries left. */
 388     unsigned freeEntries;
 389
 390     /** The number of entries in the instruction queue. */
 391     unsigned numEntries;
 392
 393     /** The total number of instructions that can be issued in one cycle. */
 394     unsigned totalWidth;
 395
 396     /** The number of physical registers in the CPU. */
 397     unsigned numPhysRegs;
 398
 399     /** The number of physical integer registers in the CPU. */
 400     unsigned numPhysIntRegs;
 401
 402     /** The number of floating point registers in the CPU. */
 403     unsigned numPhysFloatRegs;
 404
 405     /** Delay between commit stage and the IQ.
 406      *  @todo: Make there be a distinction between the delays within IEW.
 407      */
 408     unsigned commitToIEWDelay;
 409
 410     /** Is the IQ switched out. */
 411     bool switchedOut;
 412
 413     /** The sequence number of the squashed instruction. */
 414     InstSeqNum squashedSeqNum[Impl::MaxThreads];
 415
 416     /** A cache of the recently woken registers.  It is 1 if the register
 417      *  has been woken up recently, and 0 if the register has been added
 418      *  to the dependency graph and has not yet received its value.  It
 419      *  is basically a secondary scoreboard, and should pretty much mirror
 420      *  the scoreboard that exists in the rename map.
 421      */
 422     std::vector<bool> regScoreboard;
 423
 424     /** Adds an instruction to the dependency graph, as a consumer. */
 425     bool addToDependents(DynInstPtr &new_inst);
 426
 427     /** Adds an instruction to the dependency graph, as a producer. */
 428     void addToProducers(DynInstPtr &new_inst);
 429
 430     /** Moves an instruction to the ready queue if it is ready. */
 431     void addIfReady(DynInstPtr &inst);
 432
 433     /** Debugging function to count how many entries are in the IQ.  It does
 434      *  a linear walk through the instructions, so do not call this function
 435      *  during normal execution.
 436      */
 437     int countInsts();
 438
 439     /** Debugging function to dump all the list sizes, as well as print
 440      *  out the list of nonspeculative instructions.  Should not be used
 441      *  in any other capacity, but it has no harmful sideaffects.
 442      */
 443     void dumpLists();
 444
 445     /** Debugging function to dump out all instructions that are in the
 446      *  IQ.
 447      */
 448     void dumpInsts();
 449
 450     /** Stat for number of instructions added. */
 451     Stats::Scalar<> iqInstsAdded;
 452     /** Stat for number of non-speculative instructions added. */
 453     Stats::Scalar<> iqNonSpecInstsAdded;
 454
 455     Stats::Scalar<> iqInstsIssued;
 456     /** Stat for number of integer instructions issued. */
 457     Stats::Scalar<> iqIntInstsIssued;
 458     /** Stat for number of floating point instructions issued. */
 459     Stats::Scalar<> iqFloatInstsIssued;
 460     /** Stat for number of branch instructions issued. */
 461     Stats::Scalar<> iqBranchInstsIssued;
 462     /** Stat for number of memory instructions issued. */
 463     Stats::Scalar<> iqMemInstsIssued;
 464     /** Stat for number of miscellaneous instructions issued. */
 465     Stats::Scalar<> iqMiscInstsIssued;
 466     /** Stat for number of squashed instructions that were ready to issue. */
 467     Stats::Scalar<> iqSquashedInstsIssued;
 468     /** Stat for number of squashed instructions examined when squashing. */
 469     Stats::Scalar<> iqSquashedInstsExamined;
 470     /** Stat for number of squashed instruction operands examined when
 471      * squashing.
 472      */
 473     Stats::Scalar<> iqSquashedOperandsExamined;
 474     /** Stat for number of non-speculative instructions removed due to a squash.
 475      */
 476     Stats::Scalar<> iqSquashedNonSpecRemoved;
 477     // Also include number of instructions rescheduled and replayed.
 478
 479     /** Distribution of number of instructions in the queue.
 480      * @todo: Need to create struct to track the entry time for each
 481      * instruction. */
 482 //    Stats::VectorDistribution<> queueResDist;
 483     /** Distribution of the number of instructions issued. */
 484     Stats::Distribution<> numIssuedDist;
 485     /** Distribution of the cycles it takes to issue an instruction.
 486      * @todo: Need to create struct to track the ready time for each
 487      * instruction. */
 488 //    Stats::VectorDistribution<> issueDelayDist;
 489
 490     /** Number of times an instruction could not be issued because a
 491      * FU was busy.
 492      */
 493     Stats::Vector<> statFuBusy;
 494 //    Stats::Vector<> dist_unissued;
 495     /** Stat for total number issued for each instruction type. */
 496     Stats::Vector2d<> statIssuedInstType;
 497
 498     /** Number of instructions issued per cycle. */
 499     Stats::Formula issueRate;
 500
 501     /** Number of times the FU was busy. */
 502     Stats::Vector<> fuBusy;
 503     /** Number of times the FU was busy per instruction issued. */
 504     Stats::Formula fuBusyRate;
 505 };
 506
 507 #endif //__CPU_O3_INST_QUEUE_HH__