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

 /*
  * Copyright (c) 2012 ARM Limited
  * 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_ROB_IMPL_HH__
 #define __CPU_O3_ROB_IMPL_HH__

 #include <list>

 #include "base/logging.hh"
 #include "cpu/o3/rob.hh"
 #include "debug/Fetch.hh"
 #include "debug/ROB.hh"
 #include "params/DerivO3CPU.hh"

 template <class Impl>
 ROB<Impl>::ROB(O3CPU *_cpu, const DerivO3CPUParams &params)
     : robPolicy(params.smtROBPolicy),
       cpu(_cpu),
       numEntries(params.numROBEntries),
       squashWidth(params.squashWidth),
       numInstsInROB(0),
       numThreads(params.numThreads),
       stats(_cpu)
 {
     //Figure out rob policy
     if (robPolicy == SMTQueuePolicy::Dynamic) {
         //Set Max Entries to Total ROB Capacity
         for (ThreadID tid = 0; tid < numThreads; tid++) {
             maxEntries[tid] = numEntries;
         }

     } else if (robPolicy == SMTQueuePolicy::Partitioned) {
         DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");

         //@todo:make work if part_amt doesnt divide evenly.
         int part_amt = numEntries / numThreads;

         //Divide ROB up evenly
         for (ThreadID tid = 0; tid < numThreads; tid++) {
             maxEntries[tid] = part_amt;
         }

     } else if (robPolicy == SMTQueuePolicy::Threshold) {
         DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");

         int threshold =  params.smtROBThreshold;;

         //Divide up by threshold amount
         for (ThreadID tid = 0; tid < numThreads; tid++) {
             maxEntries[tid] = threshold;
         }
     }

     for (ThreadID tid = numThreads; tid < Impl::MaxThreads; tid++) {
         maxEntries[tid] = 0;
     }

     resetState();
 }

 template <class Impl>
 void
 ROB<Impl>::resetState()
 {
     for (ThreadID tid = 0; tid  < Impl::MaxThreads; tid++) {
         threadEntries[tid] = 0;
         squashIt[tid] = instList[tid].end();
         squashedSeqNum[tid] = 0;
         doneSquashing[tid] = true;
     }
     numInstsInROB = 0;

     // Initialize the "universal" ROB head & tail point to invalid
     // pointers
     head = instList[0].end();
     tail = instList[0].end();
 }

 template <class Impl>
 std::string
 ROB<Impl>::name() const
 {
     return cpu->name() + ".rob";
 }

 template <class Impl>
 void
 ROB<Impl>::setActiveThreads(std::list<ThreadID> *at_ptr)
 {
     DPRINTF(ROB, "Setting active threads list pointer.\n");
     activeThreads = at_ptr;
 }

 template <class Impl>
 void
 ROB<Impl>::drainSanityCheck() const
 {
     for (ThreadID tid = 0; tid  < numThreads; tid++)
         assert(instList[tid].empty());
     assert(isEmpty());
 }

 template <class Impl>
 void
 ROB<Impl>::takeOverFrom()
 {
     resetState();
 }

 template <class Impl>
 void
 ROB<Impl>::resetEntries()
 {
     if (robPolicy != SMTQueuePolicy::Dynamic || numThreads > 1) {
         auto active_threads = activeThreads->size();

         std::list<ThreadID>::iterator threads = activeThreads->begin();
         std::list<ThreadID>::iterator end = activeThreads->end();

         while (threads != end) {
             ThreadID tid = *threads++;

             if (robPolicy == SMTQueuePolicy::Partitioned) {
                 maxEntries[tid] = numEntries / active_threads;
             } else if (robPolicy == SMTQueuePolicy::Threshold &&
                        active_threads == 1) {
                 maxEntries[tid] = numEntries;
             }
         }
     }
 }

 template <class Impl>
 int
 ROB<Impl>::entryAmount(ThreadID num_threads)
 {
     if (robPolicy == SMTQueuePolicy::Partitioned) {
         return numEntries / num_threads;
     } else {
         return 0;
     }
 }

 template <class Impl>
 int
 ROB<Impl>::countInsts()
 {
     int total = 0;

     for (ThreadID tid = 0; tid < numThreads; tid++)
         total += countInsts(tid);

     return total;
 }

 template <class Impl>
 size_t
 ROB<Impl>::countInsts(ThreadID tid)
 {
     return instList[tid].size();
 }

 template <class Impl>
 void
 ROB<Impl>::insertInst(const DynInstPtr &inst)
 {
     assert(inst);

     stats.writes++;

     DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState());

     assert(numInstsInROB != numEntries);

     ThreadID tid = inst->threadNumber;

     instList[tid].push_back(inst);

     //Set Up head iterator if this is the 1st instruction in the ROB
     if (numInstsInROB == 0) {
         head = instList[tid].begin();
         assert((*head) == inst);
     }

     //Must Decrement for iterator to actually be valid  since __.end()
     //actually points to 1 after the last inst
     tail = instList[tid].end();
     tail--;

     inst->setInROB();

     ++numInstsInROB;
     ++threadEntries[tid];

     assert((*tail) == inst);

     DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
 }

 template <class Impl>
 void
 ROB<Impl>::retireHead(ThreadID tid)
 {
     stats.writes++;

     assert(numInstsInROB > 0);

     // Get the head ROB instruction by copying it and remove it from the list
     InstIt head_it = instList[tid].begin();

     DynInstPtr head_inst = std::move(*head_it);
     instList[tid].erase(head_it);

     assert(head_inst->readyToCommit());

     DPRINTF(ROB, "[tid:%i] Retiring head instruction, "
             "instruction PC %s, [sn:%llu]\n", tid, head_inst->pcState(),
             head_inst->seqNum);

     --numInstsInROB;
     --threadEntries[tid];

     head_inst->clearInROB();
     head_inst->setCommitted();

     //Update "Global" Head of ROB
     updateHead();

     // @todo: A special case is needed if the instruction being
     // retired is the only instruction in the ROB; otherwise the tail
     // iterator will become invalidated.
     cpu->removeFrontInst(head_inst);
 }

 template <class Impl>
 bool
 ROB<Impl>::isHeadReady(ThreadID tid)
 {
     stats.reads++;
     if (threadEntries[tid] != 0) {
         return instList[tid].front()->readyToCommit();
     }

     return false;
 }

 template <class Impl>
 bool
 ROB<Impl>::canCommit()
 {
     //@todo: set ActiveThreads through ROB or CPU
     std::list<ThreadID>::iterator threads = activeThreads->begin();
     std::list<ThreadID>::iterator end = activeThreads->end();

     while (threads != end) {
         ThreadID tid = *threads++;

         if (isHeadReady(tid)) {
             return true;
         }
     }

     return false;
 }

 template <class Impl>
 unsigned
 ROB<Impl>::numFreeEntries()
 {
     return numEntries - numInstsInROB;
 }

 template <class Impl>
 unsigned
 ROB<Impl>::numFreeEntries(ThreadID tid)
 {
     return maxEntries[tid] - threadEntries[tid];
 }

 template <class Impl>
 void
 ROB<Impl>::doSquash(ThreadID tid)
 {
     stats.writes++;
     DPRINTF(ROB, "[tid:%i] Squashing instructions until [sn:%llu].\n",
             tid, squashedSeqNum[tid]);

     assert(squashIt[tid] != instList[tid].end());

     if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
         DPRINTF(ROB, "[tid:%i] Done squashing instructions.\n",
                 tid);

         squashIt[tid] = instList[tid].end();

         doneSquashing[tid] = true;
         return;
     }

     bool robTailUpdate = false;

     unsigned int numInstsToSquash = squashWidth;

     // If the CPU is exiting, squash all of the instructions
     // it is told to, even if that exceeds the squashWidth.
     // Set the number to the number of entries (the max).
     if (cpu->isThreadExiting(tid))
     {
         numInstsToSquash = numEntries;
     }

     for (int numSquashed = 0;
          numSquashed < numInstsToSquash &&
          squashIt[tid] != instList[tid].end() &&
          (*squashIt[tid])->seqNum > squashedSeqNum[tid];
          ++numSquashed)
     {
         DPRINTF(ROB, "[tid:%i] Squashing instruction PC %s, seq num %i.\n",
                 (*squashIt[tid])->threadNumber,
                 (*squashIt[tid])->pcState(),
                 (*squashIt[tid])->seqNum);

         // Mark the instruction as squashed, and ready to commit so that
         // it can drain out of the pipeline.
         (*squashIt[tid])->setSquashed();

         (*squashIt[tid])->setCanCommit();


         if (squashIt[tid] == instList[tid].begin()) {
             DPRINTF(ROB, "Reached head of instruction list while "
                     "squashing.\n");

             squashIt[tid] = instList[tid].end();

             doneSquashing[tid] = true;

             return;
         }

         InstIt tail_thread = instList[tid].end();
         tail_thread--;

         if ((*squashIt[tid]) == (*tail_thread))
             robTailUpdate = true;

         squashIt[tid]--;
     }


     // Check if ROB is done squashing.
     if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
         DPRINTF(ROB, "[tid:%i] Done squashing instructions.\n",
                 tid);

         squashIt[tid] = instList[tid].end();

         doneSquashing[tid] = true;
     }

     if (robTailUpdate) {
         updateTail();
     }
 }


 template <class Impl>
 void
 ROB<Impl>::updateHead()
 {
     InstSeqNum lowest_num = 0;
     bool first_valid = true;

     // @todo: set ActiveThreads through ROB or CPU
     std::list<ThreadID>::iterator threads = activeThreads->begin();
     std::list<ThreadID>::iterator end = activeThreads->end();

     while (threads != end) {
         ThreadID tid = *threads++;

         if (instList[tid].empty())
             continue;

         if (first_valid) {
             head = instList[tid].begin();
             lowest_num = (*head)->seqNum;
             first_valid = false;
             continue;
         }

         InstIt head_thread = instList[tid].begin();

         DynInstPtr head_inst = (*head_thread);

         assert(head_inst != 0);

         if (head_inst->seqNum < lowest_num) {
             head = head_thread;
             lowest_num = head_inst->seqNum;
         }
     }

     if (first_valid) {
         head = instList[0].end();
     }

 }

 template <class Impl>
 void
 ROB<Impl>::updateTail()
 {
     tail = instList[0].end();
     bool first_valid = true;

     std::list<ThreadID>::iterator threads = activeThreads->begin();
     std::list<ThreadID>::iterator end = activeThreads->end();

     while (threads != end) {
         ThreadID tid = *threads++;

         if (instList[tid].empty()) {
             continue;
         }

         // If this is the first valid then assign w/out
         // comparison
         if (first_valid) {
             tail = instList[tid].end();
             tail--;
             first_valid = false;
             continue;
         }

         // Assign new tail if this thread's tail is younger
         // than our current "tail high"
         InstIt tail_thread = instList[tid].end();
         tail_thread--;

         if ((*tail_thread)->seqNum > (*tail)->seqNum) {
             tail = tail_thread;
         }
     }
 }


 template <class Impl>
 void
 ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid)
 {
     if (isEmpty(tid)) {
         DPRINTF(ROB, "Does not need to squash due to being empty "
                 "[sn:%llu]\n",
                 squash_num);

         return;
     }

     DPRINTF(ROB, "Starting to squash within the ROB.\n");

     robStatus[tid] = ROBSquashing;

     doneSquashing[tid] = false;

     squashedSeqNum[tid] = squash_num;

     if (!instList[tid].empty()) {
         InstIt tail_thread = instList[tid].end();
         tail_thread--;

         squashIt[tid] = tail_thread;

         doSquash(tid);
     }
 }

 template <class Impl>
 const typename Impl::DynInstPtr&
 ROB<Impl>::readHeadInst(ThreadID tid)
 {
     if (threadEntries[tid] != 0) {
         InstIt head_thread = instList[tid].begin();

         assert((*head_thread)->isInROB());

         return *head_thread;
     } else {
         return dummyInst;
     }
 }

 template <class Impl>
 typename Impl::DynInstPtr
 ROB<Impl>::readTailInst(ThreadID tid)
 {
     InstIt tail_thread = instList[tid].end();
     tail_thread--;

     return *tail_thread;
 }

 template <class Impl>
 ROB<Impl>::ROBStats::ROBStats(Stats::Group *parent)
     : Stats::Group(parent, "rob"),
       ADD_STAT(reads, UNIT_COUNT, "The number of ROB reads"),
       ADD_STAT(writes, UNIT_COUNT, "The number of ROB writes")
 {
 }

 template <class Impl>
 typename Impl::DynInstPtr
 ROB<Impl>::findInst(ThreadID tid, InstSeqNum squash_inst)
 {
     for (InstIt it = instList[tid].begin(); it != instList[tid].end(); it++) {
         if ((*it)->seqNum == squash_inst) {
             return *it;
         }
     }
     return NULL;
 }

 #endif//__CPU_O3_ROB_IMPL_HH__
	/*
	* Copyright (c) 2012 ARM Limited
	* 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_ROB_IMPL_HH__
	#define __CPU_O3_ROB_IMPL_HH__

	#include <list>

	#include "base/logging.hh"
	#include "cpu/o3/rob.hh"
	#include "debug/Fetch.hh"
	#include "debug/ROB.hh"
	#include "params/DerivO3CPU.hh"

	template <class Impl>
	ROB<Impl>::ROB(O3CPU *_cpu, const DerivO3CPUParams &params)
	: robPolicy(params.smtROBPolicy),
	cpu(_cpu),
	numEntries(params.numROBEntries),
	squashWidth(params.squashWidth),
	numInstsInROB(0),
	numThreads(params.numThreads),
	stats(_cpu)
	{
	//Figure out rob policy
	if (robPolicy == SMTQueuePolicy::Dynamic) {
	//Set Max Entries to Total ROB Capacity
	for (ThreadID tid = 0; tid < numThreads; tid++) {
	maxEntries[tid] = numEntries;
	}

	} else if (robPolicy == SMTQueuePolicy::Partitioned) {
	DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");

	//@todo:make work if part_amt doesnt divide evenly.
	int part_amt = numEntries / numThreads;

	//Divide ROB up evenly
	for (ThreadID tid = 0; tid < numThreads; tid++) {
	maxEntries[tid] = part_amt;
	}

	} else if (robPolicy == SMTQueuePolicy::Threshold) {
	DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");

	int threshold = params.smtROBThreshold;;

	//Divide up by threshold amount
	for (ThreadID tid = 0; tid < numThreads; tid++) {
	maxEntries[tid] = threshold;
	}
	}

	for (ThreadID tid = numThreads; tid < Impl::MaxThreads; tid++) {
	maxEntries[tid] = 0;
	}

	resetState();
	}

	template <class Impl>
	void
	ROB<Impl>::resetState()
	{
	for (ThreadID tid = 0; tid < Impl::MaxThreads; tid++) {
	threadEntries[tid] = 0;
	squashIt[tid] = instList[tid].end();
	squashedSeqNum[tid] = 0;
	doneSquashing[tid] = true;
	}
	numInstsInROB = 0;

	// Initialize the "universal" ROB head & tail point to invalid
	// pointers
	head = instList[0].end();
	tail = instList[0].end();
	}

	template <class Impl>
	std::string
	ROB<Impl>::name() const
	{
	return cpu->name() + ".rob";
	}

	template <class Impl>
	void
	ROB<Impl>::setActiveThreads(std::list<ThreadID> *at_ptr)
	{
	DPRINTF(ROB, "Setting active threads list pointer.\n");
	activeThreads = at_ptr;
	}

	template <class Impl>
	void
	ROB<Impl>::drainSanityCheck() const
	{
	for (ThreadID tid = 0; tid < numThreads; tid++)
	assert(instList[tid].empty());
	assert(isEmpty());
	}

	template <class Impl>
	void
	ROB<Impl>::takeOverFrom()
	{
	resetState();
	}

	template <class Impl>
	void
	ROB<Impl>::resetEntries()
	{
	if (robPolicy != SMTQueuePolicy::Dynamic \|\| numThreads > 1) {
	auto active_threads = activeThreads->size();

	std::list<ThreadID>::iterator threads = activeThreads->begin();
	std::list<ThreadID>::iterator end = activeThreads->end();

	while (threads != end) {
	ThreadID tid = *threads++;

	if (robPolicy == SMTQueuePolicy::Partitioned) {
	maxEntries[tid] = numEntries / active_threads;
	} else if (robPolicy == SMTQueuePolicy::Threshold &&
	active_threads == 1) {
	maxEntries[tid] = numEntries;
	}
	}
	}
	}

	template <class Impl>
	int
	ROB<Impl>::entryAmount(ThreadID num_threads)
	{
	if (robPolicy == SMTQueuePolicy::Partitioned) {
	return numEntries / num_threads;
	} else {
	return 0;
	}
	}

	template <class Impl>
	int
	ROB<Impl>::countInsts()
	{
	int total = 0;

	for (ThreadID tid = 0; tid < numThreads; tid++)
	total += countInsts(tid);

	return total;
	}

	template <class Impl>
	size_t
	ROB<Impl>::countInsts(ThreadID tid)
	{
	return instList[tid].size();
	}

	template <class Impl>
	void
	ROB<Impl>::insertInst(const DynInstPtr &inst)
	{
	assert(inst);

	stats.writes++;

	DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState());

	assert(numInstsInROB != numEntries);

	ThreadID tid = inst->threadNumber;

	instList[tid].push_back(inst);

	//Set Up head iterator if this is the 1st instruction in the ROB
	if (numInstsInROB == 0) {
	head = instList[tid].begin();
	assert((*head) == inst);
	}

	//Must Decrement for iterator to actually be valid since __.end()
	//actually points to 1 after the last inst
	tail = instList[tid].end();
	tail--;

	inst->setInROB();

	++numInstsInROB;
	++threadEntries[tid];

	assert((*tail) == inst);

	DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
	}

	template <class Impl>
	void
	ROB<Impl>::retireHead(ThreadID tid)
	{
	stats.writes++;

	assert(numInstsInROB > 0);

	// Get the head ROB instruction by copying it and remove it from the list
	InstIt head_it = instList[tid].begin();

	DynInstPtr head_inst = std::move(*head_it);
	instList[tid].erase(head_it);

	assert(head_inst->readyToCommit());

	DPRINTF(ROB, "[tid:%i] Retiring head instruction, "
	"instruction PC %s, [sn:%llu]\n", tid, head_inst->pcState(),
	head_inst->seqNum);

	--numInstsInROB;
	--threadEntries[tid];

	head_inst->clearInROB();
	head_inst->setCommitted();

	//Update "Global" Head of ROB
	updateHead();

	// @todo: A special case is needed if the instruction being
	// retired is the only instruction in the ROB; otherwise the tail
	// iterator will become invalidated.
	cpu->removeFrontInst(head_inst);
	}

	template <class Impl>
	bool
	ROB<Impl>::isHeadReady(ThreadID tid)
	{
	stats.reads++;
	if (threadEntries[tid] != 0) {
	return instList[tid].front()->readyToCommit();
	}

	return false;
	}

	template <class Impl>
	bool
	ROB<Impl>::canCommit()
	{
	//@todo: set ActiveThreads through ROB or CPU
	std::list<ThreadID>::iterator threads = activeThreads->begin();
	std::list<ThreadID>::iterator end = activeThreads->end();

	while (threads != end) {
	ThreadID tid = *threads++;

	if (isHeadReady(tid)) {
	return true;
	}
	}

	return false;
	}

	template <class Impl>
	unsigned
	ROB<Impl>::numFreeEntries()
	{
	return numEntries - numInstsInROB;
	}

	template <class Impl>
	unsigned
	ROB<Impl>::numFreeEntries(ThreadID tid)
	{
	return maxEntries[tid] - threadEntries[tid];
	}

	template <class Impl>
	void
	ROB<Impl>::doSquash(ThreadID tid)
	{
	stats.writes++;
	DPRINTF(ROB, "[tid:%i] Squashing instructions until [sn:%llu].\n",
	tid, squashedSeqNum[tid]);

	assert(squashIt[tid] != instList[tid].end());

	if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
	DPRINTF(ROB, "[tid:%i] Done squashing instructions.\n",
	tid);

	squashIt[tid] = instList[tid].end();

	doneSquashing[tid] = true;
	return;
	}

	bool robTailUpdate = false;

	unsigned int numInstsToSquash = squashWidth;

	// If the CPU is exiting, squash all of the instructions
	// it is told to, even if that exceeds the squashWidth.
	// Set the number to the number of entries (the max).
	if (cpu->isThreadExiting(tid))
	{
	numInstsToSquash = numEntries;
	}

	for (int numSquashed = 0;
	numSquashed < numInstsToSquash &&
	squashIt[tid] != instList[tid].end() &&
	(*squashIt[tid])->seqNum > squashedSeqNum[tid];
	++numSquashed)
	{
	DPRINTF(ROB, "[tid:%i] Squashing instruction PC %s, seq num %i.\n",
	(*squashIt[tid])->threadNumber,
	(*squashIt[tid])->pcState(),
	(*squashIt[tid])->seqNum);

	// Mark the instruction as squashed, and ready to commit so that
	// it can drain out of the pipeline.
	(*squashIt[tid])->setSquashed();

	(*squashIt[tid])->setCanCommit();


	if (squashIt[tid] == instList[tid].begin()) {
	DPRINTF(ROB, "Reached head of instruction list while "
	"squashing.\n");

	squashIt[tid] = instList[tid].end();

	doneSquashing[tid] = true;

	return;
	}

	InstIt tail_thread = instList[tid].end();
	tail_thread--;

	if ((squashIt[tid]) == (tail_thread))
	robTailUpdate = true;

	squashIt[tid]--;
	}


	// Check if ROB is done squashing.
	if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
	DPRINTF(ROB, "[tid:%i] Done squashing instructions.\n",
	tid);

	squashIt[tid] = instList[tid].end();

	doneSquashing[tid] = true;
	}

	if (robTailUpdate) {
	updateTail();
	}
	}


	template <class Impl>
	void
	ROB<Impl>::updateHead()
	{
	InstSeqNum lowest_num = 0;
	bool first_valid = true;

	// @todo: set ActiveThreads through ROB or CPU
	std::list<ThreadID>::iterator threads = activeThreads->begin();
	std::list<ThreadID>::iterator end = activeThreads->end();

	while (threads != end) {
	ThreadID tid = *threads++;

	if (instList[tid].empty())
	continue;

	if (first_valid) {
	head = instList[tid].begin();
	lowest_num = (*head)->seqNum;
	first_valid = false;
	continue;
	}

	InstIt head_thread = instList[tid].begin();

	DynInstPtr head_inst = (*head_thread);

	assert(head_inst != 0);

	if (head_inst->seqNum < lowest_num) {
	head = head_thread;
	lowest_num = head_inst->seqNum;
	}
	}

	if (first_valid) {
	head = instList[0].end();
	}

	}

	template <class Impl>
	void
	ROB<Impl>::updateTail()
	{
	tail = instList[0].end();
	bool first_valid = true;

	std::list<ThreadID>::iterator threads = activeThreads->begin();
	std::list<ThreadID>::iterator end = activeThreads->end();

	while (threads != end) {
	ThreadID tid = *threads++;

	if (instList[tid].empty()) {
	continue;
	}

	// If this is the first valid then assign w/out
	// comparison
	if (first_valid) {
	tail = instList[tid].end();
	tail--;
	first_valid = false;
	continue;
	}

	// Assign new tail if this thread's tail is younger
	// than our current "tail high"
	InstIt tail_thread = instList[tid].end();
	tail_thread--;

	if ((tail_thread)->seqNum > (tail)->seqNum) {
	tail = tail_thread;
	}
	}
	}


	template <class Impl>
	void
	ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid)
	{
	if (isEmpty(tid)) {
	DPRINTF(ROB, "Does not need to squash due to being empty "
	"[sn:%llu]\n",
	squash_num);

	return;
	}

	DPRINTF(ROB, "Starting to squash within the ROB.\n");

	robStatus[tid] = ROBSquashing;

	doneSquashing[tid] = false;

	squashedSeqNum[tid] = squash_num;

	if (!instList[tid].empty()) {
	InstIt tail_thread = instList[tid].end();
	tail_thread--;

	squashIt[tid] = tail_thread;

	doSquash(tid);
	}
	}

	template <class Impl>
	const typename Impl::DynInstPtr&
	ROB<Impl>::readHeadInst(ThreadID tid)
	{
	if (threadEntries[tid] != 0) {
	InstIt head_thread = instList[tid].begin();

	assert((*head_thread)->isInROB());

	return *head_thread;
	} else {
	return dummyInst;
	}
	}

	template <class Impl>
	typename Impl::DynInstPtr
	ROB<Impl>::readTailInst(ThreadID tid)
	{
	InstIt tail_thread = instList[tid].end();
	tail_thread--;

	return *tail_thread;
	}

	template <class Impl>
	ROB<Impl>::ROBStats::ROBStats(Stats::Group *parent)
	: Stats::Group(parent, "rob"),
	ADD_STAT(reads, UNIT_COUNT, "The number of ROB reads"),
	ADD_STAT(writes, UNIT_COUNT, "The number of ROB writes")
	{
	}

	template <class Impl>
	typename Impl::DynInstPtr
	ROB<Impl>::findInst(ThreadID tid, InstSeqNum squash_inst)
	{
	for (InstIt it = instList[tid].begin(); it != instList[tid].end(); it++) {
	if ((*it)->seqNum == squash_inst) {
	return *it;
	}
	}
	return NULL;
	}

	#endif//__CPU_O3_ROB_IMPL_HH__