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(unsigned _numEntries, unsigned _squashWidth,
39 string _smtROBPolicy, unsigned _smtROBThreshold,
41 : numEntries(_numEntries),
42 squashWidth(_squashWidth),
45 numThreads(_numThreads)
47 for (int tid=0; tid < numThreads; tid++) {
48 doneSquashing[tid] = true;
49 threadEntries[tid] = 0;
52 string policy = _smtROBPolicy;
54 //Convert string to lowercase
55 std::transform(policy.begin(), policy.end(), policy.begin(),
56 (int(*)(int)) tolower);
58 //Figure out rob policy
59 if (policy == "dynamic") {
62 //Set Max Entries to Total ROB Capacity
63 for (int i = 0; i < numThreads; i++) {
64 maxEntries[i]=numEntries;
67 } else if (policy == "partitioned") {
68 robPolicy = Partitioned;
69 DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");
71 //@todo:make work if part_amt doesnt divide evenly.
72 int part_amt = numEntries / numThreads;
74 //Divide ROB up evenly
75 for (int i = 0; i < numThreads; i++) {
76 maxEntries[i]=part_amt;
79 } else if (policy == "threshold") {
80 robPolicy = Threshold;
81 DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");
83 int threshold = _smtROBThreshold;;
85 //Divide up by threshold amount
86 for (int i = 0; i < numThreads; i++) {
87 maxEntries[i]=threshold;
90 assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic,"
91 "Partitioned, Threshold}");
97 ROB<Impl>::name() const
99 return cpu->name() + ".rob";
102 template <class Impl>
104 ROB<Impl>::setCPU(O3CPU *cpu_ptr)
108 // Set the per-thread iterators to the end of the instruction list.
109 for (int i=0; i < numThreads;i++) {
110 squashIt[i] = instList[i].end();
113 // Initialize the "universal" ROB head & tail point to invalid
115 head = instList[0].end();
116 tail = instList[0].end();
119 template <class Impl>
121 ROB<Impl>::setActiveThreads(list<unsigned> *at_ptr)
123 DPRINTF(ROB, "Setting active threads list pointer.\n");
124 activeThreads = at_ptr;
127 template <class Impl>
129 ROB<Impl>::switchOut()
131 for (int tid = 0; tid < numThreads; tid++) {
132 instList[tid].clear();
136 template <class Impl>
138 ROB<Impl>::takeOverFrom()
140 for (int tid=0; tid < numThreads; tid++) {
141 doneSquashing[tid] = true;
142 threadEntries[tid] = 0;
143 squashIt[tid] = instList[tid].end();
147 // Initialize the "universal" ROB head & tail point to invalid
149 head = instList[0].end();
150 tail = instList[0].end();
153 template <class Impl>
155 ROB<Impl>::resetEntries()
157 if (robPolicy != Dynamic || numThreads > 1) {
158 int active_threads = (*activeThreads).size();
160 list<unsigned>::iterator threads = (*activeThreads).begin();
161 list<unsigned>::iterator list_end = (*activeThreads).end();
163 while (threads != list_end) {
164 if (robPolicy == Partitioned) {
165 maxEntries[*threads++] = numEntries / active_threads;
166 } else if (robPolicy == Threshold && active_threads == 1) {
167 maxEntries[*threads++] = numEntries;
173 template <class Impl>
175 ROB<Impl>::entryAmount(int num_threads)
177 if (robPolicy == Partitioned) {
178 return numEntries / num_threads;
184 template <class Impl>
186 ROB<Impl>::countInsts()
190 for (int i=0;i < numThreads;i++)
191 total += countInsts(i);
196 template <class Impl>
198 ROB<Impl>::countInsts(unsigned tid)
200 return instList[tid].size();
203 template <class Impl>
205 ROB<Impl>::insertInst(DynInstPtr &inst)
207 //assert(numInstsInROB == countInsts());
210 DPRINTF(ROB, "Adding inst PC %#x to the ROB.\n", inst->readPC());
212 assert(numInstsInROB != numEntries);
214 int tid = inst->threadNumber;
216 instList[tid].push_back(inst);
218 //Set Up head iterator if this is the 1st instruction in the ROB
219 if (numInstsInROB == 0) {
220 head = instList[tid].begin();
221 assert((*head) == inst);
224 //Must Decrement for iterator to actually be valid since __.end()
225 //actually points to 1 after the last inst
226 tail = instList[tid].end();
232 ++threadEntries[tid];
234 assert((*tail) == inst);
236 DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
239 // Whatever calls this function needs to ensure that it properly frees up
240 // registers prior to this function.
242 template <class Impl>
244 ROB<Impl>::retireHead()
246 //assert(numInstsInROB == countInsts());
247 assert(numInstsInROB > 0);
249 int tid = (*head)->threadNumber;
253 if (numInstsInROB == 0) {
254 tail = instList[tid].end();
259 template <class Impl>
261 ROB<Impl>::retireHead(unsigned tid)
263 //assert(numInstsInROB == countInsts());
264 assert(numInstsInROB > 0);
266 // Get the head ROB instruction.
267 InstIt head_it = instList[tid].begin();
269 DynInstPtr head_inst = (*head_it);
271 assert(head_inst->readyToCommit());
273 DPRINTF(ROB, "[tid:%u]: Retiring head instruction, "
274 "instruction PC %#x,[sn:%lli]\n", tid, head_inst->readPC(),
278 --threadEntries[tid];
280 head_inst->clearInROB();
281 head_inst->setCommitted();
283 instList[tid].erase(head_it);
285 //Update "Global" Head of ROB
288 // @todo: A special case is needed if the instruction being
289 // retired is the only instruction in the ROB; otherwise the tail
290 // iterator will become invalidated.
291 cpu->removeFrontInst(head_inst);
294 template <class Impl>
296 ROB<Impl>::isHeadReady()
298 if (numInstsInROB != 0) {
299 return (*head)->readyToCommit();
305 template <class Impl>
307 ROB<Impl>::isHeadReady(unsigned tid)
309 if (threadEntries[tid] != 0) {
310 return instList[tid].front()->readyToCommit();
316 template <class Impl>
318 ROB<Impl>::canCommit()
320 //@todo: set ActiveThreads through ROB or CPU
321 list<unsigned>::iterator threads = (*activeThreads).begin();
323 while (threads != (*activeThreads).end()) {
324 unsigned tid = *threads++;
326 if (isHeadReady(tid)) {
334 template <class Impl>
336 ROB<Impl>::numFreeEntries()
338 //assert(numInstsInROB == countInsts());
340 return numEntries - numInstsInROB;
343 template <class Impl>
345 ROB<Impl>::numFreeEntries(unsigned tid)
347 return maxEntries[tid] - threadEntries[tid];
350 template <class Impl>
352 ROB<Impl>::doSquash(unsigned tid)
354 DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n",
355 tid, squashedSeqNum);
357 assert(squashIt[tid] != instList[tid].end());
359 if ((*squashIt[tid])->seqNum < squashedSeqNum) {
360 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
363 squashIt[tid] = instList[tid].end();
365 doneSquashing[tid] = true;
369 bool robTailUpdate = false;
371 for (int numSquashed = 0;
372 numSquashed < squashWidth &&
373 squashIt[tid] != instList[tid].end() &&
374 (*squashIt[tid])->seqNum > squashedSeqNum;
377 DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %#x, seq num %i.\n",
378 (*squashIt[tid])->threadNumber,
379 (*squashIt[tid])->readPC(),
380 (*squashIt[tid])->seqNum);
382 // Mark the instruction as squashed, and ready to commit so that
383 // it can drain out of the pipeline.
384 (*squashIt[tid])->setSquashed();
386 (*squashIt[tid])->setCanCommit();
389 if (squashIt[tid] == instList[tid].begin()) {
390 DPRINTF(ROB, "Reached head of instruction list while "
393 squashIt[tid] = instList[tid].end();
395 doneSquashing[tid] = true;
400 InstIt tail_thread = instList[tid].end();
403 if ((*squashIt[tid]) == (*tail_thread))
404 robTailUpdate = true;
410 // Check if ROB is done squashing.
411 if ((*squashIt[tid])->seqNum <= squashedSeqNum) {
412 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
415 squashIt[tid] = instList[tid].end();
417 doneSquashing[tid] = true;
426 template <class Impl>
428 ROB<Impl>::updateHead()
430 DynInstPtr head_inst;
431 InstSeqNum lowest_num = 0;
432 bool first_valid = true;
434 // @todo: set ActiveThreads through ROB or CPU
435 list<unsigned>::iterator threads = (*activeThreads).begin();
437 while (threads != (*activeThreads).end()) {
438 unsigned thread_num = *threads++;
440 if (instList[thread_num].empty())
444 head = instList[thread_num].begin();
445 lowest_num = (*head)->seqNum;
450 InstIt head_thread = instList[thread_num].begin();
452 DynInstPtr head_inst = (*head_thread);
454 assert(head_inst != 0);
456 if (head_inst->seqNum < lowest_num) {
458 lowest_num = head_inst->seqNum;
463 head = instList[0].end();
468 template <class Impl>
470 ROB<Impl>::updateTail()
472 tail = instList[0].end();
473 bool first_valid = true;
475 list<unsigned>::iterator threads = (*activeThreads).begin();
477 while (threads != (*activeThreads).end()) {
478 unsigned tid = *threads++;
480 if (instList[tid].empty()) {
484 // If this is the first valid then assign w/out
487 tail = instList[tid].end();
493 // Assign new tail if this thread's tail is younger
494 // than our current "tail high"
495 InstIt tail_thread = instList[tid].end();
498 if ((*tail_thread)->seqNum > (*tail)->seqNum) {
505 template <class Impl>
507 ROB<Impl>::squash(InstSeqNum squash_num,unsigned tid)
510 DPRINTF(ROB, "Does not need to squash due to being empty "
517 DPRINTF(ROB, "Starting to squash within the ROB.\n");
519 robStatus[tid] = ROBSquashing;
521 doneSquashing[tid] = false;
523 squashedSeqNum = squash_num;
525 if (!instList[tid].empty()) {
526 InstIt tail_thread = instList[tid].end();
529 squashIt[tid] = tail_thread;
535 template <class Impl>
536 typename Impl::DynInstPtr
537 ROB<Impl>::readHeadInst()
539 if (numInstsInROB != 0) {
540 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);
562 template <class Impl>
564 ROB<Impl>::readHeadPC()
566 //assert(numInstsInROB == countInsts());
568 DynInstPtr head_inst = *head;
570 return head_inst->readPC();
573 template <class Impl>
575 ROB<Impl>::readHeadPC(unsigned tid)
577 //assert(numInstsInROB == countInsts());
578 InstIt head_thread = instList[tid].begin();
580 return (*head_thread)->readPC();
584 template <class Impl>
586 ROB<Impl>::readHeadNextPC()
588 //assert(numInstsInROB == countInsts());
590 DynInstPtr head_inst = *head;
592 return head_inst->readNextPC();
595 template <class Impl>
597 ROB<Impl>::readHeadNextPC(unsigned tid)
599 //assert(numInstsInROB == countInsts());
600 InstIt head_thread = instList[tid].begin();
602 return (*head_thread)->readNextPC();
605 template <class Impl>
607 ROB<Impl>::readHeadSeqNum()
609 //assert(numInstsInROB == countInsts());
610 DynInstPtr head_inst = *head;
612 return head_inst->seqNum;
615 template <class Impl>
617 ROB<Impl>::readHeadSeqNum(unsigned tid)
619 InstIt head_thread = instList[tid].begin();
621 return ((*head_thread)->seqNum);
624 template <class Impl>
625 typename Impl::DynInstPtr
626 ROB<Impl>::readTailInst()
628 //assert(numInstsInROB == countInsts());
629 //assert(tail != instList[0].end());
634 template <class Impl>
635 typename Impl::DynInstPtr
636 ROB<Impl>::readTailInst(unsigned tid)
638 //assert(tail_thread[tid] != instList[tid].end());
640 InstIt tail_thread = instList[tid].end();
647 template <class Impl>
649 ROB<Impl>::readTailPC()
651 //assert(numInstsInROB == countInsts());
653 //assert(tail != instList[0].end());
655 return (*tail)->readPC();
658 template <class Impl>
660 ROB<Impl>::readTailPC(unsigned tid)
662 //assert(tail_thread[tid] != instList[tid].end());
664 InstIt tail_thread = instList[tid].end();
667 return (*tail_thread)->readPC();
670 template <class Impl>
672 ROB<Impl>::readTailSeqNum()
674 // Return the last sequence number that has not been squashed. Other
675 // stages can use it to squash any instructions younger than the current
677 return (*tail)->seqNum;
680 template <class Impl>
682 ROB<Impl>::readTailSeqNum(unsigned tid)
684 // Return the last sequence number that has not been squashed. Other
685 // stages can use it to squash any instructions younger than the current
687 // assert(tail_thread[tid] != instList[tid].end());
689 InstIt tail_thread = instList[tid].end();
692 return (*tail_thread)->seqNum;