src/cpu/o3/inst_queue.hh

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