src/cpu/o3/inst_queue.hh

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