src/cpu/o3/inst_queue.hh - public/gem5 - Git at Google

 /*
  * Copyright (c) 2011-2012, 2014 ARM Limited
  * Copyright (c) 2013 Advanced Micro Devices, Inc.
  * All rights reserved.
  *
  * The license below extends only to copyright in the software and shall
  * not be construed as granting a license to any other intellectual
  * property including but not limited to intellectual property relating
  * to a hardware implementation of the functionality of the software
  * licensed hereunder.  You may use the software subject to the license
  * terms below provided that you ensure that this notice is replicated
  * unmodified and in its entirety in all distributions of the software,
  * modified or unmodified, in source code or in binary form.
  *
  * Copyright (c) 2004-2006 The Regents of The University of Michigan
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met: redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer;
  * redistributions in binary form must reproduce the above copyright
  * notice, this list of conditions and the following disclaimer in the
  * documentation and/or other materials provided with the distribution;
  * neither the name of the copyright holders nor the names of its
  * contributors may be used to endorse or promote products derived from
  * this software without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */

 #ifndef __CPU_O3_INST_QUEUE_HH__
 #define __CPU_O3_INST_QUEUE_HH__

 #include <list>
 #include <map>
 #include <queue>
 #include <vector>

 #include "base/statistics.hh"
 #include "base/types.hh"
 #include "cpu/o3/dep_graph.hh"
 #include "cpu/inst_seq.hh"
 #include "cpu/op_class.hh"
 #include "cpu/timebuf.hh"
 #include "enums/SMTQueuePolicy.hh"
 #include "sim/eventq.hh"

 struct DerivO3CPUParams;
 class FUPool;
 class MemInterface;

 /**
  * A standard instruction queue class.  It holds ready instructions, in
  * order, in seperate priority queues to facilitate the scheduling of
  * instructions.  The IQ uses a separate linked list to track dependencies.
  * Similar to the rename map and the free list, it expects that
  * floating point registers have their indices start after the integer
  * registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
  * and 96-191 are fp).  This remains true even for both logical and
  * physical register indices. The IQ depends on the memory dependence unit to
  * track when memory operations are ready in terms of ordering; register
  * dependencies are tracked normally. Right now the IQ also handles the
  * execution timing; this is mainly to allow back-to-back scheduling without
  * requiring IEW to be able to peek into the IQ. At the end of the execution
  * latency, the instruction is put into the queue to execute, where it will
  * have the execute() function called on it.
  * @todo: Make IQ able to handle multiple FU pools.
  */
 template <class Impl>
 class InstructionQueue
 {
   public:
     //Typedefs from the Impl.
     typedef typename Impl::O3CPU O3CPU;
     typedef typename Impl::DynInstPtr DynInstPtr;

     typedef typename Impl::CPUPol::IEW IEW;
     typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
     typedef typename Impl::CPUPol::IssueStruct IssueStruct;
     typedef typename Impl::CPUPol::TimeStruct TimeStruct;

     // Typedef of iterator through the list of instructions.
     typedef typename std::list<DynInstPtr>::iterator ListIt;

     /** FU completion event class. */
     class FUCompletion : public Event {
       private:
         /** Executing instruction. */
         DynInstPtr inst;

         /** Index of the FU used for executing. */
         int fuIdx;

         /** Pointer back to the instruction queue. */
         InstructionQueue<Impl> *iqPtr;

         /** Should the FU be added to the list to be freed upon
          * completing this event.
          */
         bool freeFU;

       public:
         /** Construct a FU completion event. */
         FUCompletion(const DynInstPtr &_inst, int fu_idx,
                      InstructionQueue<Impl> *iq_ptr);

         virtual void process();
         virtual const char *description() const;
         void setFreeFU() { freeFU = true; }
     };

     /** Constructs an IQ. */
     InstructionQueue(O3CPU *cpu_ptr, IEW *iew_ptr,
                      const DerivO3CPUParams &params);

     /** Destructs the IQ. */
     ~InstructionQueue();

     /** Returns the name of the IQ. */
     std::string name() const;

     /** Resets all instruction queue state. */
     void resetState();

     /** Sets active threads list. */
     void setActiveThreads(std::list<ThreadID> *at_ptr);

     /** Sets the timer buffer between issue and execute. */
     void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);

     /** Sets the global time buffer. */
     void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);

     /** Determine if we are drained. */
     bool isDrained() const;

     /** Perform sanity checks after a drain. */
     void drainSanityCheck() const;

     /** Takes over execution from another CPU's thread. */
     void takeOverFrom();

     /** Number of entries needed for given amount of threads. */
     int entryAmount(ThreadID num_threads);

     /** Resets max entries for all threads. */
     void resetEntries();

     /** Returns total number of free entries. */
     unsigned numFreeEntries();

     /** Returns number of free entries for a thread. */
     unsigned numFreeEntries(ThreadID tid);

     /** Returns whether or not the IQ is full. */
     bool isFull();

     /** Returns whether or not the IQ is full for a specific thread. */
     bool isFull(ThreadID tid);

     /** Returns if there are any ready instructions in the IQ. */
     bool hasReadyInsts();

     /** Inserts a new instruction into the IQ. */
     void insert(const DynInstPtr &new_inst);

     /** Inserts a new, non-speculative instruction into the IQ. */
     void insertNonSpec(const DynInstPtr &new_inst);

     /** Inserts a memory or write barrier into the IQ to make sure
      *  loads and stores are ordered properly.
      */
     void insertBarrier(const DynInstPtr &barr_inst);

     /** Returns the oldest scheduled instruction, and removes it from
      * the list of instructions waiting to execute.
      */
     DynInstPtr getInstToExecute();

     /** Gets a memory instruction that was referred due to a delayed DTB
      *  translation if it is now ready to execute.  NULL if none available.
      */
     DynInstPtr getDeferredMemInstToExecute();

     /** Gets a memory instruction that was blocked on the cache. NULL if none
      *  available.
      */
     DynInstPtr getBlockedMemInstToExecute();

     /**
      * Records the instruction as the producer of a register without
      * adding it to the rest of the IQ.
      */
     void recordProducer(const DynInstPtr &inst)
     { addToProducers(inst); }

     /** Process FU completion event. */
     void processFUCompletion(const DynInstPtr &inst, int fu_idx);

     /**
      * Schedules ready instructions, adding the ready ones (oldest first) to
      * the queue to execute.
      */
     void scheduleReadyInsts();

     /** Schedules a single specific non-speculative instruction. */
     void scheduleNonSpec(const InstSeqNum &inst);

     /**
      * Commits all instructions up to and including the given sequence number,
      * for a specific thread.
      */
     void commit(const InstSeqNum &inst, ThreadID tid = 0);

     /** Wakes all dependents of a completed instruction. */
     int wakeDependents(const DynInstPtr &completed_inst);

     /** Adds a ready memory instruction to the ready list. */
     void addReadyMemInst(const DynInstPtr &ready_inst);

     /**
      * Reschedules a memory instruction. It will be ready to issue once
      * replayMemInst() is called.
      */
     void rescheduleMemInst(const DynInstPtr &resched_inst);

     /** Replays a memory instruction. It must be rescheduled first. */
     void replayMemInst(const DynInstPtr &replay_inst);

     /**
      * Defers a memory instruction when its DTB translation incurs a hw
      * page table walk.
      */
     void deferMemInst(const DynInstPtr &deferred_inst);

     /**  Defers a memory instruction when it is cache blocked. */
     void blockMemInst(const DynInstPtr &blocked_inst);

     /**  Notify instruction queue that a previous blockage has resolved */
     void cacheUnblocked();

     /** Indicates an ordering violation between a store and a load. */
     void violation(const DynInstPtr &store, const DynInstPtr &faulting_load);

     /**
      * Squashes instructions for a thread. Squashing information is obtained
      * from the time buffer.
      */
     void squash(ThreadID tid);

     /** Returns the number of used entries for a thread. */
     unsigned getCount(ThreadID tid) { return count[tid]; };

     /** Debug function to print all instructions. */
     void printInsts();

   private:
     /** Does the actual squashing. */
     void doSquash(ThreadID tid);

     /////////////////////////
     // Various pointers
     /////////////////////////

     /** Pointer to the CPU. */
     O3CPU *cpu;

     /** Cache interface. */
     MemInterface *dcacheInterface;

     /** Pointer to IEW stage. */
     IEW *iewStage;

     /** The memory dependence unit, which tracks/predicts memory dependences
      *  between instructions.
      */
     MemDepUnit memDepUnit[Impl::MaxThreads];

     /** The queue to the execute stage.  Issued instructions will be written
      *  into it.
      */
     TimeBuffer<IssueStruct> *issueToExecuteQueue;

     /** The backwards time buffer. */
     TimeBuffer<TimeStruct> *timeBuffer;

     /** Wire to read information from timebuffer. */
     typename TimeBuffer<TimeStruct>::wire fromCommit;

     /** Function unit pool. */
     FUPool *fuPool;

     //////////////////////////////////////
     // Instruction lists, ready queues, and ordering
     //////////////////////////////////////

     /** List of all the instructions in the IQ (some of which may be issued). */
     std::list<DynInstPtr> instList[Impl::MaxThreads];

     /** List of instructions that are ready to be executed. */
     std::list<DynInstPtr> instsToExecute;

     /** List of instructions waiting for their DTB translation to
      *  complete (hw page table walk in progress).
      */
     std::list<DynInstPtr> deferredMemInsts;

     /** List of instructions that have been cache blocked. */
     std::list<DynInstPtr> blockedMemInsts;

     /** List of instructions that were cache blocked, but a retry has been seen
      * since, so they can now be retried. May fail again go on the blocked list.
      */
     std::list<DynInstPtr> retryMemInsts;

     /**
      * Struct for comparing entries to be added to the priority queue.
      * This gives reverse ordering to the instructions in terms of
      * sequence numbers: the instructions with smaller sequence
      * numbers (and hence are older) will be at the top of the
      * priority queue.
      */
     struct pqCompare {
         bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
         {
             return lhs->seqNum > rhs->seqNum;
         }
     };

     typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
     ReadyInstQueue;

     /** List of ready instructions, per op class.  They are separated by op
      *  class to allow for easy mapping to FUs.
      */
     ReadyInstQueue readyInsts[Num_OpClasses];

     /** List of non-speculative instructions that will be scheduled
      *  once the IQ gets a signal from commit.  While it's redundant to
      *  have the key be a part of the value (the sequence number is stored
      *  inside of DynInst), when these instructions are woken up only
      *  the sequence number will be available.  Thus it is most efficient to be
      *  able to search by the sequence number alone.
      */
     std::map<InstSeqNum, DynInstPtr> nonSpecInsts;

     typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;

     /** Entry for the list age ordering by op class. */
     struct ListOrderEntry {
         OpClass queueType;
         InstSeqNum oldestInst;
     };

     /** List that contains the age order of the oldest instruction of each
      *  ready queue.  Used to select the oldest instruction available
      *  among op classes.
      *  @todo: Might be better to just move these entries around instead
      *  of creating new ones every time the position changes due to an
      *  instruction issuing.  Not sure std::list supports this.
      */
     std::list<ListOrderEntry> listOrder;

     typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;

     /** Tracks if each ready queue is on the age order list. */
     bool queueOnList[Num_OpClasses];

     /** Iterators of each ready queue.  Points to their spot in the age order
      *  list.
      */
     ListOrderIt readyIt[Num_OpClasses];

     /** Add an op class to the age order list. */
     void addToOrderList(OpClass op_class);

     /**
      * Called when the oldest instruction has been removed from a ready queue;
      * this places that ready queue into the proper spot in the age order list.
      */
     void moveToYoungerInst(ListOrderIt age_order_it);

     DependencyGraph<DynInstPtr> dependGraph;

     //////////////////////////////////////
     // Various parameters
     //////////////////////////////////////

     /** IQ sharing policy for SMT. */
     SMTQueuePolicy iqPolicy;

     /** Number of Total Threads*/
     ThreadID numThreads;

     /** Pointer to list of active threads. */
     std::list<ThreadID> *activeThreads;

     /** Per Thread IQ count */
     unsigned count[Impl::MaxThreads];

     /** Max IQ Entries Per Thread */
     unsigned maxEntries[Impl::MaxThreads];

     /** Number of free IQ entries left. */
     unsigned freeEntries;

     /** The number of entries in the instruction queue. */
     unsigned numEntries;

     /** The total number of instructions that can be issued in one cycle. */
     unsigned totalWidth;

     /** The number of physical registers in the CPU. */
     unsigned numPhysRegs;

     /** Number of instructions currently in flight to FUs */
     int wbOutstanding;

     /** Delay between commit stage and the IQ.
      *  @todo: Make there be a distinction between the delays within IEW.
      */
     Cycles commitToIEWDelay;

     /** The sequence number of the squashed instruction. */
     InstSeqNum squashedSeqNum[Impl::MaxThreads];

     /** A cache of the recently woken registers.  It is 1 if the register
      *  has been woken up recently, and 0 if the register has been added
      *  to the dependency graph and has not yet received its value.  It
      *  is basically a secondary scoreboard, and should pretty much mirror
      *  the scoreboard that exists in the rename map.
      */
     std::vector<bool> regScoreboard;

     /** Adds an instruction to the dependency graph, as a consumer. */
     bool addToDependents(const DynInstPtr &new_inst);

     /** Adds an instruction to the dependency graph, as a producer. */
     void addToProducers(const DynInstPtr &new_inst);

     /** Moves an instruction to the ready queue if it is ready. */
     void addIfReady(const DynInstPtr &inst);

     /** Debugging function to count how many entries are in the IQ.  It does
      *  a linear walk through the instructions, so do not call this function
      *  during normal execution.
      */
     int countInsts();

     /** Debugging function to dump all the list sizes, as well as print
      *  out the list of nonspeculative instructions.  Should not be used
      *  in any other capacity, but it has no harmful sideaffects.
      */
     void dumpLists();

     /** Debugging function to dump out all instructions that are in the
      *  IQ.
      */
     void dumpInsts();

     struct IQStats : public Stats::Group
     {
         IQStats(O3CPU *cpu, const unsigned &total_width);
         /** Stat for number of instructions added. */
         Stats::Scalar instsAdded;
         /** Stat for number of non-speculative instructions added. */
         Stats::Scalar nonSpecInstsAdded;

         Stats::Scalar instsIssued;
         /** Stat for number of integer instructions issued. */
         Stats::Scalar intInstsIssued;
         /** Stat for number of floating point instructions issued. */
         Stats::Scalar floatInstsIssued;
         /** Stat for number of branch instructions issued. */
         Stats::Scalar branchInstsIssued;
         /** Stat for number of memory instructions issued. */
         Stats::Scalar memInstsIssued;
         /** Stat for number of miscellaneous instructions issued. */
         Stats::Scalar miscInstsIssued;
         /** Stat for number of squashed instructions that were ready to
          *  issue. */
         Stats::Scalar squashedInstsIssued;
         /** Stat for number of squashed instructions examined when
          *  squashing. */
         Stats::Scalar squashedInstsExamined;
         /** Stat for number of squashed instruction operands examined when
          * squashing.
          */
         Stats::Scalar squashedOperandsExamined;
         /** Stat for number of non-speculative instructions removed due to
          *  a squash.
          */
         Stats::Scalar squashedNonSpecRemoved;
         // Also include number of instructions rescheduled and replayed.

         /** Distribution of number of instructions in the queue.
          * @todo: Need to create struct to track the entry time for each
          * instruction. */
         // Stats::VectorDistribution queueResDist;
         /** Distribution of the number of instructions issued. */
         Stats::Distribution numIssuedDist;
         /** Distribution of the cycles it takes to issue an instruction.
          * @todo: Need to create struct to track the ready time for each
          * instruction. */
         // Stats::VectorDistribution issueDelayDist;

         /** Number of times an instruction could not be issued because a
          * FU was busy.
          */
         Stats::Vector statFuBusy;
         // Stats::Vector dist_unissued;
         /** Stat for total number issued for each instruction type. */
         Stats::Vector2d statIssuedInstType;

         /** Number of instructions issued per cycle. */
         Stats::Formula issueRate;

         /** Number of times the FU was busy. */
         Stats::Vector fuBusy;
         /** Number of times the FU was busy per instruction issued. */
         Stats::Formula fuBusyRate;
     } iqStats;

    public:
     struct IQIOStats : public Stats::Group
     {
         IQIOStats(Stats::Group *parent);
         Stats::Scalar intInstQueueReads;
         Stats::Scalar intInstQueueWrites;
         Stats::Scalar intInstQueueWakeupAccesses;
         Stats::Scalar fpInstQueueReads;
         Stats::Scalar fpInstQueueWrites;
         Stats::Scalar fpInstQueueWakeupAccesses;
         Stats::Scalar vecInstQueueReads;
         Stats::Scalar vecInstQueueWrites;
         Stats::Scalar vecInstQueueWakeupAccesses;

         Stats::Scalar intAluAccesses;
         Stats::Scalar fpAluAccesses;
         Stats::Scalar vecAluAccesses;
     } iqIOStats;
 };

 #endif //__CPU_O3_INST_QUEUE_HH__
	/*
	* Copyright (c) 2011-2012, 2014 ARM Limited
	* Copyright (c) 2013 Advanced Micro Devices, Inc.
	* All rights reserved.
	*
	* The license below extends only to copyright in the software and shall
	* not be construed as granting a license to any other intellectual
	* property including but not limited to intellectual property relating
	* to a hardware implementation of the functionality of the software
	* licensed hereunder. You may use the software subject to the license
	* terms below provided that you ensure that this notice is replicated
	* unmodified and in its entirety in all distributions of the software,
	* modified or unmodified, in source code or in binary form.
	*
	* Copyright (c) 2004-2006 The Regents of The University of Michigan
	* All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions are
	* met: redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer;
	* redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution;
	* neither the name of the copyright holders nor the names of its
	* contributors may be used to endorse or promote products derived from
	* this software without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/

	#ifndef __CPU_O3_INST_QUEUE_HH__
	#define __CPU_O3_INST_QUEUE_HH__

	#include <list>
	#include <map>
	#include <queue>
	#include <vector>

	#include "base/statistics.hh"
	#include "base/types.hh"
	#include "cpu/o3/dep_graph.hh"
	#include "cpu/inst_seq.hh"
	#include "cpu/op_class.hh"
	#include "cpu/timebuf.hh"
	#include "enums/SMTQueuePolicy.hh"
	#include "sim/eventq.hh"

	struct DerivO3CPUParams;
	class FUPool;
	class MemInterface;

	/**
	* A standard instruction queue class. It holds ready instructions, in
	* order, in seperate priority queues to facilitate the scheduling of
	* instructions. The IQ uses a separate linked list to track dependencies.
	* Similar to the rename map and the free list, it expects that
	* floating point registers have their indices start after the integer
	* registers (ie with 96 int and 96 fp registers, regs 0-95 are integer
	* and 96-191 are fp). This remains true even for both logical and
	* physical register indices. The IQ depends on the memory dependence unit to
	* track when memory operations are ready in terms of ordering; register
	* dependencies are tracked normally. Right now the IQ also handles the
	* execution timing; this is mainly to allow back-to-back scheduling without
	* requiring IEW to be able to peek into the IQ. At the end of the execution
	* latency, the instruction is put into the queue to execute, where it will
	* have the execute() function called on it.
	* @todo: Make IQ able to handle multiple FU pools.
	*/
	template <class Impl>
	class InstructionQueue
	{
	public:
	//Typedefs from the Impl.
	typedef typename Impl::O3CPU O3CPU;
	typedef typename Impl::DynInstPtr DynInstPtr;

	typedef typename Impl::CPUPol::IEW IEW;
	typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
	typedef typename Impl::CPUPol::IssueStruct IssueStruct;
	typedef typename Impl::CPUPol::TimeStruct TimeStruct;

	// Typedef of iterator through the list of instructions.
	typedef typename std::list<DynInstPtr>::iterator ListIt;

	/** FU completion event class. */
	class FUCompletion : public Event {
	private:
	/** Executing instruction. */
	DynInstPtr inst;

	/** Index of the FU used for executing. */
	int fuIdx;

	/** Pointer back to the instruction queue. */
	InstructionQueue<Impl> *iqPtr;

	/** Should the FU be added to the list to be freed upon
	* completing this event.
	*/
	bool freeFU;

	public:
	/** Construct a FU completion event. */
	FUCompletion(const DynInstPtr &_inst, int fu_idx,
	InstructionQueue<Impl> *iq_ptr);

	virtual void process();
	virtual const char *description() const;
	void setFreeFU() { freeFU = true; }
	};

	/** Constructs an IQ. */
	InstructionQueue(O3CPU cpu_ptr, IEW iew_ptr,
	const DerivO3CPUParams &params);

	/** Destructs the IQ. */
	~InstructionQueue();

	/** Returns the name of the IQ. */
	std::string name() const;

	/** Resets all instruction queue state. */
	void resetState();

	/** Sets active threads list. */
	void setActiveThreads(std::list<ThreadID> *at_ptr);

	/** Sets the timer buffer between issue and execute. */
	void setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2eQueue);

	/** Sets the global time buffer. */
	void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);

	/** Determine if we are drained. */
	bool isDrained() const;

	/** Perform sanity checks after a drain. */
	void drainSanityCheck() const;

	/** Takes over execution from another CPU's thread. */
	void takeOverFrom();

	/** Number of entries needed for given amount of threads. */
	int entryAmount(ThreadID num_threads);

	/** Resets max entries for all threads. */
	void resetEntries();

	/** Returns total number of free entries. */
	unsigned numFreeEntries();

	/** Returns number of free entries for a thread. */
	unsigned numFreeEntries(ThreadID tid);

	/** Returns whether or not the IQ is full. */
	bool isFull();

	/** Returns whether or not the IQ is full for a specific thread. */
	bool isFull(ThreadID tid);

	/** Returns if there are any ready instructions in the IQ. */
	bool hasReadyInsts();

	/** Inserts a new instruction into the IQ. */
	void insert(const DynInstPtr &new_inst);

	/** Inserts a new, non-speculative instruction into the IQ. */
	void insertNonSpec(const DynInstPtr &new_inst);

	/** Inserts a memory or write barrier into the IQ to make sure
	* loads and stores are ordered properly.
	*/
	void insertBarrier(const DynInstPtr &barr_inst);

	/** Returns the oldest scheduled instruction, and removes it from
	* the list of instructions waiting to execute.
	*/
	DynInstPtr getInstToExecute();

	/** Gets a memory instruction that was referred due to a delayed DTB
	* translation if it is now ready to execute. NULL if none available.
	*/
	DynInstPtr getDeferredMemInstToExecute();

	/** Gets a memory instruction that was blocked on the cache. NULL if none
	* available.
	*/
	DynInstPtr getBlockedMemInstToExecute();

	/**
	* Records the instruction as the producer of a register without
	* adding it to the rest of the IQ.
	*/
	void recordProducer(const DynInstPtr &inst)
	{ addToProducers(inst); }

	/** Process FU completion event. */
	void processFUCompletion(const DynInstPtr &inst, int fu_idx);

	/**
	* Schedules ready instructions, adding the ready ones (oldest first) to
	* the queue to execute.
	*/
	void scheduleReadyInsts();

	/** Schedules a single specific non-speculative instruction. */
	void scheduleNonSpec(const InstSeqNum &inst);

	/**
	* Commits all instructions up to and including the given sequence number,
	* for a specific thread.
	*/
	void commit(const InstSeqNum &inst, ThreadID tid = 0);

	/** Wakes all dependents of a completed instruction. */
	int wakeDependents(const DynInstPtr &completed_inst);

	/** Adds a ready memory instruction to the ready list. */
	void addReadyMemInst(const DynInstPtr &ready_inst);

	/**
	* Reschedules a memory instruction. It will be ready to issue once
	* replayMemInst() is called.
	*/
	void rescheduleMemInst(const DynInstPtr &resched_inst);

	/** Replays a memory instruction. It must be rescheduled first. */
	void replayMemInst(const DynInstPtr &replay_inst);

	/**
	* Defers a memory instruction when its DTB translation incurs a hw
	* page table walk.
	*/
	void deferMemInst(const DynInstPtr &deferred_inst);

	/** Defers a memory instruction when it is cache blocked. */
	void blockMemInst(const DynInstPtr &blocked_inst);

	/** Notify instruction queue that a previous blockage has resolved */
	void cacheUnblocked();

	/** Indicates an ordering violation between a store and a load. */
	void violation(const DynInstPtr &store, const DynInstPtr &faulting_load);

	/**
	* Squashes instructions for a thread. Squashing information is obtained
	* from the time buffer.
	*/
	void squash(ThreadID tid);

	/** Returns the number of used entries for a thread. */
	unsigned getCount(ThreadID tid) { return count[tid]; };

	/** Debug function to print all instructions. */
	void printInsts();

	private:
	/** Does the actual squashing. */
	void doSquash(ThreadID tid);

	/////////////////////////
	// Various pointers
	/////////////////////////

	/** Pointer to the CPU. */
	O3CPU *cpu;

	/** Cache interface. */
	MemInterface *dcacheInterface;

	/** Pointer to IEW stage. */
	IEW *iewStage;

	/** The memory dependence unit, which tracks/predicts memory dependences
	* between instructions.
	*/
	MemDepUnit memDepUnit[Impl::MaxThreads];

	/** The queue to the execute stage. Issued instructions will be written
	* into it.
	*/
	TimeBuffer<IssueStruct> *issueToExecuteQueue;

	/** The backwards time buffer. */
	TimeBuffer<TimeStruct> *timeBuffer;

	/** Wire to read information from timebuffer. */
	typename TimeBuffer<TimeStruct>::wire fromCommit;

	/** Function unit pool. */
	FUPool *fuPool;

	//////////////////////////////////////
	// Instruction lists, ready queues, and ordering
	//////////////////////////////////////

	/** List of all the instructions in the IQ (some of which may be issued). */
	std::list<DynInstPtr> instList[Impl::MaxThreads];

	/** List of instructions that are ready to be executed. */
	std::list<DynInstPtr> instsToExecute;

	/** List of instructions waiting for their DTB translation to
	* complete (hw page table walk in progress).
	*/
	std::list<DynInstPtr> deferredMemInsts;

	/** List of instructions that have been cache blocked. */
	std::list<DynInstPtr> blockedMemInsts;

	/** List of instructions that were cache blocked, but a retry has been seen
	* since, so they can now be retried. May fail again go on the blocked list.
	*/
	std::list<DynInstPtr> retryMemInsts;

	/**
	* Struct for comparing entries to be added to the priority queue.
	* This gives reverse ordering to the instructions in terms of
	* sequence numbers: the instructions with smaller sequence
	* numbers (and hence are older) will be at the top of the
	* priority queue.
	*/
	struct pqCompare {
	bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
	{
	return lhs->seqNum > rhs->seqNum;
	}
	};

	typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
	ReadyInstQueue;

	/** List of ready instructions, per op class. They are separated by op
	* class to allow for easy mapping to FUs.
	*/
	ReadyInstQueue readyInsts[Num_OpClasses];

	/** List of non-speculative instructions that will be scheduled
	* once the IQ gets a signal from commit. While it's redundant to
	* have the key be a part of the value (the sequence number is stored
	* inside of DynInst), when these instructions are woken up only
	* the sequence number will be available. Thus it is most efficient to be
	* able to search by the sequence number alone.
	*/
	std::map<InstSeqNum, DynInstPtr> nonSpecInsts;

	typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;

	/** Entry for the list age ordering by op class. */
	struct ListOrderEntry {
	OpClass queueType;
	InstSeqNum oldestInst;
	};

	/** List that contains the age order of the oldest instruction of each
	* ready queue. Used to select the oldest instruction available
	* among op classes.
	* @todo: Might be better to just move these entries around instead
	* of creating new ones every time the position changes due to an
	* instruction issuing. Not sure std::list supports this.
	*/
	std::list<ListOrderEntry> listOrder;

	typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;

	/** Tracks if each ready queue is on the age order list. */
	bool queueOnList[Num_OpClasses];

	/** Iterators of each ready queue. Points to their spot in the age order
	* list.
	*/
	ListOrderIt readyIt[Num_OpClasses];

	/** Add an op class to the age order list. */
	void addToOrderList(OpClass op_class);

	/**
	* Called when the oldest instruction has been removed from a ready queue;
	* this places that ready queue into the proper spot in the age order list.
	*/
	void moveToYoungerInst(ListOrderIt age_order_it);

	DependencyGraph<DynInstPtr> dependGraph;

	//////////////////////////////////////
	// Various parameters
	//////////////////////////////////////

	/** IQ sharing policy for SMT. */
	SMTQueuePolicy iqPolicy;

	/** Number of Total Threads*/
	ThreadID numThreads;

	/** Pointer to list of active threads. */
	std::list<ThreadID> *activeThreads;

	/** Per Thread IQ count */
	unsigned count[Impl::MaxThreads];

	/** Max IQ Entries Per Thread */
	unsigned maxEntries[Impl::MaxThreads];

	/** Number of free IQ entries left. */
	unsigned freeEntries;

	/** The number of entries in the instruction queue. */
	unsigned numEntries;

	/** The total number of instructions that can be issued in one cycle. */
	unsigned totalWidth;

	/** The number of physical registers in the CPU. */
	unsigned numPhysRegs;

	/** Number of instructions currently in flight to FUs */
	int wbOutstanding;

	/** Delay between commit stage and the IQ.
	* @todo: Make there be a distinction between the delays within IEW.
	*/
	Cycles commitToIEWDelay;

	/** The sequence number of the squashed instruction. */
	InstSeqNum squashedSeqNum[Impl::MaxThreads];

	/** A cache of the recently woken registers. It is 1 if the register
	* has been woken up recently, and 0 if the register has been added
	* to the dependency graph and has not yet received its value. It
	* is basically a secondary scoreboard, and should pretty much mirror
	* the scoreboard that exists in the rename map.
	*/
	std::vector<bool> regScoreboard;

	/** Adds an instruction to the dependency graph, as a consumer. */
	bool addToDependents(const DynInstPtr &new_inst);

	/** Adds an instruction to the dependency graph, as a producer. */
	void addToProducers(const DynInstPtr &new_inst);

	/** Moves an instruction to the ready queue if it is ready. */
	void addIfReady(const DynInstPtr &inst);

	/** Debugging function to count how many entries are in the IQ. It does
	* a linear walk through the instructions, so do not call this function
	* during normal execution.
	*/
	int countInsts();

	/** Debugging function to dump all the list sizes, as well as print
	* out the list of nonspeculative instructions. Should not be used
	* in any other capacity, but it has no harmful sideaffects.
	*/
	void dumpLists();

	/** Debugging function to dump out all instructions that are in the
	* IQ.
	*/
	void dumpInsts();

	struct IQStats : public Stats::Group
	{
	IQStats(O3CPU *cpu, const unsigned &total_width);
	/** Stat for number of instructions added. */
	Stats::Scalar instsAdded;
	/** Stat for number of non-speculative instructions added. */
	Stats::Scalar nonSpecInstsAdded;

	Stats::Scalar instsIssued;
	/** Stat for number of integer instructions issued. */
	Stats::Scalar intInstsIssued;
	/** Stat for number of floating point instructions issued. */
	Stats::Scalar floatInstsIssued;
	/** Stat for number of branch instructions issued. */
	Stats::Scalar branchInstsIssued;
	/** Stat for number of memory instructions issued. */
	Stats::Scalar memInstsIssued;
	/** Stat for number of miscellaneous instructions issued. */
	Stats::Scalar miscInstsIssued;
	/** Stat for number of squashed instructions that were ready to
	* issue. */
	Stats::Scalar squashedInstsIssued;
	/** Stat for number of squashed instructions examined when
	* squashing. */
	Stats::Scalar squashedInstsExamined;
	/** Stat for number of squashed instruction operands examined when
	* squashing.
	*/
	Stats::Scalar squashedOperandsExamined;
	/** Stat for number of non-speculative instructions removed due to
	* a squash.
	*/
	Stats::Scalar squashedNonSpecRemoved;
	// Also include number of instructions rescheduled and replayed.

	/** Distribution of number of instructions in the queue.
	* @todo: Need to create struct to track the entry time for each
	* instruction. */
	// Stats::VectorDistribution queueResDist;
	/** Distribution of the number of instructions issued. */
	Stats::Distribution numIssuedDist;
	/** Distribution of the cycles it takes to issue an instruction.
	* @todo: Need to create struct to track the ready time for each
	* instruction. */
	// Stats::VectorDistribution issueDelayDist;

	/** Number of times an instruction could not be issued because a
	* FU was busy.
	*/
	Stats::Vector statFuBusy;
	// Stats::Vector dist_unissued;
	/** Stat for total number issued for each instruction type. */
	Stats::Vector2d statIssuedInstType;

	/** Number of instructions issued per cycle. */
	Stats::Formula issueRate;

	/** Number of times the FU was busy. */
	Stats::Vector fuBusy;
	/** Number of times the FU was busy per instruction issued. */
	Stats::Formula fuBusyRate;
	} iqStats;

	public:
	struct IQIOStats : public Stats::Group
	{
	IQIOStats(Stats::Group *parent);
	Stats::Scalar intInstQueueReads;
	Stats::Scalar intInstQueueWrites;
	Stats::Scalar intInstQueueWakeupAccesses;
	Stats::Scalar fpInstQueueReads;
	Stats::Scalar fpInstQueueWrites;
	Stats::Scalar fpInstQueueWakeupAccesses;
	Stats::Scalar vecInstQueueReads;
	Stats::Scalar vecInstQueueWrites;
	Stats::Scalar vecInstQueueWakeupAccesses;

	Stats::Scalar intAluAccesses;
	Stats::Scalar fpAluAccesses;
	Stats::Scalar vecAluAccesses;
	} iqIOStats;
	};

	#endif //__CPU_O3_INST_QUEUE_HH__