2 * Copyright (c) 2004-2006 The Regents of The University of Michigan
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 #include "config/full_system.hh"
33 #include "cpu/o3/rob.hh"
38 ROB<Impl>::ROB(O3CPU *_cpu, unsigned _numEntries, unsigned _squashWidth,
39 std::string _smtROBPolicy, unsigned _smtROBThreshold,
42 numEntries(_numEntries),
43 squashWidth(_squashWidth),
45 numThreads(_numThreads)
47 for (int tid=0; tid < numThreads; tid++) {
48 squashedSeqNum[tid] = 0;
49 doneSquashing[tid] = true;
50 threadEntries[tid] = 0;
53 std::string policy = _smtROBPolicy;
55 //Convert string to lowercase
56 std::transform(policy.begin(), policy.end(), policy.begin(),
57 (int(*)(int)) tolower);
59 //Figure out rob policy
60 if (policy == "dynamic") {
63 //Set Max Entries to Total ROB Capacity
64 for (int i = 0; i < numThreads; i++) {
65 maxEntries[i]=numEntries;
68 } else if (policy == "partitioned") {
69 robPolicy = Partitioned;
70 DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");
72 //@todo:make work if part_amt doesnt divide evenly.
73 int part_amt = numEntries / numThreads;
75 //Divide ROB up evenly
76 for (int i = 0; i < numThreads; i++) {
77 maxEntries[i]=part_amt;
80 } else if (policy == "threshold") {
81 robPolicy = Threshold;
82 DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");
84 int threshold = _smtROBThreshold;;
86 //Divide up by threshold amount
87 for (int i = 0; i < numThreads; i++) {
88 maxEntries[i]=threshold;
91 assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic,"
92 "Partitioned, Threshold}");
95 // Set the per-thread iterators to the end of the instruction list.
96 for (int i=0; i < numThreads;i++) {
97 squashIt[i] = instList[i].end();
100 // Initialize the "universal" ROB head & tail point to invalid
102 head = instList[0].end();
103 tail = instList[0].end();
106 template <class Impl>
108 ROB<Impl>::name() const
110 return cpu->name() + ".rob";
113 template <class Impl>
115 ROB<Impl>::setActiveThreads(std::list<unsigned> *at_ptr)
117 DPRINTF(ROB, "Setting active threads list pointer.\n");
118 activeThreads = at_ptr;
121 template <class Impl>
123 ROB<Impl>::switchOut()
125 for (int tid = 0; tid < numThreads; tid++) {
126 instList[tid].clear();
130 template <class Impl>
132 ROB<Impl>::takeOverFrom()
134 for (int tid=0; tid < numThreads; tid++) {
135 doneSquashing[tid] = true;
136 threadEntries[tid] = 0;
137 squashIt[tid] = instList[tid].end();
141 // Initialize the "universal" ROB head & tail point to invalid
143 head = instList[0].end();
144 tail = instList[0].end();
147 template <class Impl>
149 ROB<Impl>::resetEntries()
151 if (robPolicy != Dynamic || numThreads > 1) {
152 int active_threads = activeThreads->size();
154 std::list<unsigned>::iterator threads = activeThreads->begin();
155 std::list<unsigned>::iterator end = activeThreads->end();
157 while (threads != end) {
158 unsigned tid = *threads++;
160 if (robPolicy == Partitioned) {
161 maxEntries[tid] = numEntries / active_threads;
162 } else if (robPolicy == Threshold && active_threads == 1) {
163 maxEntries[tid] = numEntries;
169 template <class Impl>
171 ROB<Impl>::entryAmount(int num_threads)
173 if (robPolicy == Partitioned) {
174 return numEntries / num_threads;
180 template <class Impl>
182 ROB<Impl>::countInsts()
186 for (int i=0;i < numThreads;i++)
187 total += countInsts(i);
192 template <class Impl>
194 ROB<Impl>::countInsts(unsigned tid)
196 return instList[tid].size();
199 template <class Impl>
201 ROB<Impl>::insertInst(DynInstPtr &inst)
203 //assert(numInstsInROB == countInsts());
206 DPRINTF(ROB, "Adding inst PC %#x to the ROB.\n", inst->readPC());
208 assert(numInstsInROB != numEntries);
210 int tid = inst->threadNumber;
212 instList[tid].push_back(inst);
214 //Set Up head iterator if this is the 1st instruction in the ROB
215 if (numInstsInROB == 0) {
216 head = instList[tid].begin();
217 assert((*head) == inst);
220 //Must Decrement for iterator to actually be valid since __.end()
221 //actually points to 1 after the last inst
222 tail = instList[tid].end();
228 ++threadEntries[tid];
230 assert((*tail) == inst);
232 DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
235 // Whatever calls this function needs to ensure that it properly frees up
236 // registers prior to this function.
238 template <class Impl>
240 ROB<Impl>::retireHead()
242 //assert(numInstsInROB == countInsts());
243 assert(numInstsInROB > 0);
245 int tid = (*head)->threadNumber;
249 if (numInstsInROB == 0) {
250 tail = instList[tid].end();
255 template <class Impl>
257 ROB<Impl>::retireHead(unsigned tid)
259 //assert(numInstsInROB == countInsts());
260 assert(numInstsInROB > 0);
262 // Get the head ROB instruction.
263 InstIt head_it = instList[tid].begin();
265 DynInstPtr head_inst = (*head_it);
267 assert(head_inst->readyToCommit());
269 DPRINTF(ROB, "[tid:%u]: Retiring head instruction, "
270 "instruction PC %#x,[sn:%lli]\n", tid, head_inst->readPC(),
274 --threadEntries[tid];
276 head_inst->clearInROB();
277 head_inst->setCommitted();
279 instList[tid].erase(head_it);
281 //Update "Global" Head of ROB
284 // @todo: A special case is needed if the instruction being
285 // retired is the only instruction in the ROB; otherwise the tail
286 // iterator will become invalidated.
287 cpu->removeFrontInst(head_inst);
290 template <class Impl>
292 ROB<Impl>::isHeadReady()
294 if (numInstsInROB != 0) {
295 return (*head)->readyToCommit();
301 template <class Impl>
303 ROB<Impl>::isHeadReady(unsigned tid)
305 if (threadEntries[tid] != 0) {
306 return instList[tid].front()->readyToCommit();
312 template <class Impl>
314 ROB<Impl>::canCommit()
316 //@todo: set ActiveThreads through ROB or CPU
317 std::list<unsigned>::iterator threads = activeThreads->begin();
318 std::list<unsigned>::iterator end = activeThreads->end();
320 while (threads != end) {
321 unsigned tid = *threads++;
323 if (isHeadReady(tid)) {
331 template <class Impl>
333 ROB<Impl>::numFreeEntries()
335 //assert(numInstsInROB == countInsts());
337 return numEntries - numInstsInROB;
340 template <class Impl>
342 ROB<Impl>::numFreeEntries(unsigned tid)
344 return maxEntries[tid] - threadEntries[tid];
347 template <class Impl>
349 ROB<Impl>::doSquash(unsigned tid)
351 DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n",
352 tid, squashedSeqNum[tid]);
354 assert(squashIt[tid] != instList[tid].end());
356 if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
357 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
360 squashIt[tid] = instList[tid].end();
362 doneSquashing[tid] = true;
366 bool robTailUpdate = false;
368 for (int numSquashed = 0;
369 numSquashed < squashWidth &&
370 squashIt[tid] != instList[tid].end() &&
371 (*squashIt[tid])->seqNum > squashedSeqNum[tid];
374 DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %#x, seq num %i.\n",
375 (*squashIt[tid])->threadNumber,
376 (*squashIt[tid])->readPC(),
377 (*squashIt[tid])->seqNum);
379 // Mark the instruction as squashed, and ready to commit so that
380 // it can drain out of the pipeline.
381 (*squashIt[tid])->setSquashed();
383 (*squashIt[tid])->setCanCommit();
386 if (squashIt[tid] == instList[tid].begin()) {
387 DPRINTF(ROB, "Reached head of instruction list while "
390 squashIt[tid] = instList[tid].end();
392 doneSquashing[tid] = true;
397 InstIt tail_thread = instList[tid].end();
400 if ((*squashIt[tid]) == (*tail_thread))
401 robTailUpdate = true;
407 // Check if ROB is done squashing.
408 if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
409 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
412 squashIt[tid] = instList[tid].end();
414 doneSquashing[tid] = true;
423 template <class Impl>
425 ROB<Impl>::updateHead()
427 DynInstPtr head_inst;
428 InstSeqNum lowest_num = 0;
429 bool first_valid = true;
431 // @todo: set ActiveThreads through ROB or CPU
432 std::list<unsigned>::iterator threads = activeThreads->begin();
433 std::list<unsigned>::iterator end = activeThreads->end();
435 while (threads != end) {
436 unsigned tid = *threads++;
438 if (instList[tid].empty())
442 head = instList[tid].begin();
443 lowest_num = (*head)->seqNum;
448 InstIt head_thread = instList[tid].begin();
450 DynInstPtr head_inst = (*head_thread);
452 assert(head_inst != 0);
454 if (head_inst->seqNum < lowest_num) {
456 lowest_num = head_inst->seqNum;
461 head = instList[0].end();
466 template <class Impl>
468 ROB<Impl>::updateTail()
470 tail = instList[0].end();
471 bool first_valid = true;
473 std::list<unsigned>::iterator threads = activeThreads->begin();
474 std::list<unsigned>::iterator end = activeThreads->end();
476 while (threads != end) {
477 unsigned tid = *threads++;
479 if (instList[tid].empty()) {
483 // If this is the first valid then assign w/out
486 tail = instList[tid].end();
492 // Assign new tail if this thread's tail is younger
493 // than our current "tail high"
494 InstIt tail_thread = instList[tid].end();
497 if ((*tail_thread)->seqNum > (*tail)->seqNum) {
504 template <class Impl>
506 ROB<Impl>::squash(InstSeqNum squash_num,unsigned tid)
509 DPRINTF(ROB, "Does not need to squash due to being empty "
516 DPRINTF(ROB, "Starting to squash within the ROB.\n");
518 robStatus[tid] = ROBSquashing;
520 doneSquashing[tid] = false;
522 squashedSeqNum[tid] = squash_num;
524 if (!instList[tid].empty()) {
525 InstIt tail_thread = instList[tid].end();
528 squashIt[tid] = tail_thread;
534 template <class Impl>
535 typename Impl::DynInstPtr
536 ROB<Impl>::readHeadInst()
538 if (numInstsInROB != 0) {
539 assert((*head)->isInROB()==true);
547 template <class Impl>
548 typename Impl::DynInstPtr
549 ROB<Impl>::readHeadInst(unsigned tid)
551 if (threadEntries[tid] != 0) {
552 InstIt head_thread = instList[tid].begin();
554 assert((*head_thread)->isInROB()==true);
563 template <class Impl>
565 ROB<Impl>::readHeadPC()
567 //assert(numInstsInROB == countInsts());
569 DynInstPtr head_inst = *head;
571 return head_inst->readPC();
574 template <class Impl>
576 ROB<Impl>::readHeadPC(unsigned tid)
578 //assert(numInstsInROB == countInsts());
579 InstIt head_thread = instList[tid].begin();
581 return (*head_thread)->readPC();
585 template <class Impl>
587 ROB<Impl>::readHeadNextPC()
589 //assert(numInstsInROB == countInsts());
591 DynInstPtr head_inst = *head;
593 return head_inst->readNextPC();
596 template <class Impl>
598 ROB<Impl>::readHeadNextPC(unsigned tid)
600 //assert(numInstsInROB == countInsts());
601 InstIt head_thread = instList[tid].begin();
603 return (*head_thread)->readNextPC();
606 template <class Impl>
608 ROB<Impl>::readHeadSeqNum()
610 //assert(numInstsInROB == countInsts());
611 DynInstPtr head_inst = *head;
613 return head_inst->seqNum;
616 template <class Impl>
618 ROB<Impl>::readHeadSeqNum(unsigned tid)
620 InstIt head_thread = instList[tid].begin();
622 return ((*head_thread)->seqNum);
625 template <class Impl>
626 typename Impl::DynInstPtr
627 ROB<Impl>::readTailInst()
629 //assert(numInstsInROB == countInsts());
630 //assert(tail != instList[0].end());
635 template <class Impl>
636 typename Impl::DynInstPtr
637 ROB<Impl>::readTailInst(unsigned tid)
639 //assert(tail_thread[tid] != instList[tid].end());
641 InstIt tail_thread = instList[tid].end();
648 template <class Impl>
650 ROB<Impl>::readTailPC()
652 //assert(numInstsInROB == countInsts());
654 //assert(tail != instList[0].end());
656 return (*tail)->readPC();
659 template <class Impl>
661 ROB<Impl>::readTailPC(unsigned tid)
663 //assert(tail_thread[tid] != instList[tid].end());
665 InstIt tail_thread = instList[tid].end();
668 return (*tail_thread)->readPC();
671 template <class Impl>
673 ROB<Impl>::readTailSeqNum()
675 // Return the last sequence number that has not been squashed. Other
676 // stages can use it to squash any instructions younger than the current
678 return (*tail)->seqNum;
681 template <class Impl>
683 ROB<Impl>::readTailSeqNum(unsigned tid)
685 // Return the last sequence number that has not been squashed. Other
686 // stages can use it to squash any instructions younger than the current
688 // assert(tail_thread[tid] != instList[tid].end());
690 InstIt tail_thread = instList[tid].end();
693 return (*tail_thread)->seqNum;