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.
34 #include "cpu/o3/rob.hh"
35 #include "debug/Fetch.hh"
36 #include "debug/ROB.hh"
41 ROB<Impl>::ROB(O3CPU *_cpu, unsigned _numEntries, unsigned _squashWidth,
42 std::string _smtROBPolicy, unsigned _smtROBThreshold,
45 numEntries(_numEntries),
46 squashWidth(_squashWidth),
48 numThreads(_numThreads)
50 for (ThreadID tid = 0; tid < numThreads; tid++) {
51 squashedSeqNum[tid] = 0;
52 doneSquashing[tid] = true;
53 threadEntries[tid] = 0;
56 std::string policy = _smtROBPolicy;
58 //Convert string to lowercase
59 std::transform(policy.begin(), policy.end(), policy.begin(),
60 (int(*)(int)) tolower);
62 //Figure out rob policy
63 if (policy == "dynamic") {
66 //Set Max Entries to Total ROB Capacity
67 for (ThreadID tid = 0; tid < numThreads; tid++) {
68 maxEntries[tid] = numEntries;
71 } else if (policy == "partitioned") {
72 robPolicy = Partitioned;
73 DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");
75 //@todo:make work if part_amt doesnt divide evenly.
76 int part_amt = numEntries / numThreads;
78 //Divide ROB up evenly
79 for (ThreadID tid = 0; tid < numThreads; tid++) {
80 maxEntries[tid] = part_amt;
83 } else if (policy == "threshold") {
84 robPolicy = Threshold;
85 DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");
87 int threshold = _smtROBThreshold;;
89 //Divide up by threshold amount
90 for (ThreadID tid = 0; tid < numThreads; tid++) {
91 maxEntries[tid] = threshold;
94 assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic,"
95 "Partitioned, Threshold}");
98 // Set the per-thread iterators to the end of the instruction list.
99 for (ThreadID tid = 0; tid < numThreads; tid++) {
100 squashIt[tid] = instList[tid].end();
103 // Initialize the "universal" ROB head & tail point to invalid
105 head = instList[0].end();
106 tail = instList[0].end();
109 template <class Impl>
111 ROB<Impl>::name() const
113 return cpu->name() + ".rob";
116 template <class Impl>
118 ROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr)
120 DPRINTF(ROB, "Setting active threads list pointer.\n");
121 activeThreads = at_ptr;
124 template <class Impl>
126 ROB<Impl>::switchOut()
128 for (ThreadID tid = 0; tid < numThreads; tid++) {
129 instList[tid].clear();
133 template <class Impl>
135 ROB<Impl>::takeOverFrom()
137 for (ThreadID tid = 0; tid < numThreads; tid++) {
138 doneSquashing[tid] = true;
139 threadEntries[tid] = 0;
140 squashIt[tid] = instList[tid].end();
144 // Initialize the "universal" ROB head & tail point to invalid
146 head = instList[0].end();
147 tail = instList[0].end();
150 template <class Impl>
152 ROB<Impl>::resetEntries()
154 if (robPolicy != Dynamic || numThreads > 1) {
155 int active_threads = activeThreads->size();
157 list<ThreadID>::iterator threads = activeThreads->begin();
158 list<ThreadID>::iterator end = activeThreads->end();
160 while (threads != end) {
161 ThreadID tid = *threads++;
163 if (robPolicy == Partitioned) {
164 maxEntries[tid] = numEntries / active_threads;
165 } else if (robPolicy == Threshold && active_threads == 1) {
166 maxEntries[tid] = numEntries;
172 template <class Impl>
174 ROB<Impl>::entryAmount(ThreadID num_threads)
176 if (robPolicy == Partitioned) {
177 return numEntries / num_threads;
183 template <class Impl>
185 ROB<Impl>::countInsts()
189 for (ThreadID tid = 0; tid < numThreads; tid++)
190 total += countInsts(tid);
195 template <class Impl>
197 ROB<Impl>::countInsts(ThreadID tid)
199 return instList[tid].size();
202 template <class Impl>
204 ROB<Impl>::insertInst(DynInstPtr &inst)
210 DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState());
212 assert(numInstsInROB != numEntries);
214 ThreadID 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 template <class Impl>
241 ROB<Impl>::retireHead(ThreadID tid)
245 assert(numInstsInROB > 0);
247 // Get the head ROB instruction.
248 InstIt head_it = instList[tid].begin();
250 DynInstPtr head_inst = (*head_it);
252 assert(head_inst->readyToCommit());
254 DPRINTF(ROB, "[tid:%u]: Retiring head instruction, "
255 "instruction PC %s, [sn:%lli]\n", tid, head_inst->pcState(),
259 --threadEntries[tid];
261 head_inst->clearInROB();
262 head_inst->setCommitted();
264 instList[tid].erase(head_it);
266 //Update "Global" Head of ROB
269 // @todo: A special case is needed if the instruction being
270 // retired is the only instruction in the ROB; otherwise the tail
271 // iterator will become invalidated.
272 cpu->removeFrontInst(head_inst);
275 template <class Impl>
277 ROB<Impl>::isHeadReady(ThreadID tid)
280 if (threadEntries[tid] != 0) {
281 return instList[tid].front()->readyToCommit();
287 template <class Impl>
289 ROB<Impl>::canCommit()
291 //@todo: set ActiveThreads through ROB or CPU
292 list<ThreadID>::iterator threads = activeThreads->begin();
293 list<ThreadID>::iterator end = activeThreads->end();
295 while (threads != end) {
296 ThreadID tid = *threads++;
298 if (isHeadReady(tid)) {
306 template <class Impl>
308 ROB<Impl>::numFreeEntries()
310 return numEntries - numInstsInROB;
313 template <class Impl>
315 ROB<Impl>::numFreeEntries(ThreadID tid)
317 return maxEntries[tid] - threadEntries[tid];
320 template <class Impl>
322 ROB<Impl>::doSquash(ThreadID tid)
325 DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n",
326 tid, squashedSeqNum[tid]);
328 assert(squashIt[tid] != instList[tid].end());
330 if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
331 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
334 squashIt[tid] = instList[tid].end();
336 doneSquashing[tid] = true;
340 bool robTailUpdate = false;
342 for (int numSquashed = 0;
343 numSquashed < squashWidth &&
344 squashIt[tid] != instList[tid].end() &&
345 (*squashIt[tid])->seqNum > squashedSeqNum[tid];
348 DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %s, seq num %i.\n",
349 (*squashIt[tid])->threadNumber,
350 (*squashIt[tid])->pcState(),
351 (*squashIt[tid])->seqNum);
353 // Mark the instruction as squashed, and ready to commit so that
354 // it can drain out of the pipeline.
355 (*squashIt[tid])->setSquashed();
357 (*squashIt[tid])->setCanCommit();
360 if (squashIt[tid] == instList[tid].begin()) {
361 DPRINTF(ROB, "Reached head of instruction list while "
364 squashIt[tid] = instList[tid].end();
366 doneSquashing[tid] = true;
371 InstIt tail_thread = instList[tid].end();
374 if ((*squashIt[tid]) == (*tail_thread))
375 robTailUpdate = true;
381 // Check if ROB is done squashing.
382 if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
383 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
386 squashIt[tid] = instList[tid].end();
388 doneSquashing[tid] = true;
397 template <class Impl>
399 ROB<Impl>::updateHead()
401 DynInstPtr head_inst;
402 InstSeqNum lowest_num = 0;
403 bool first_valid = true;
405 // @todo: set ActiveThreads through ROB or CPU
406 list<ThreadID>::iterator threads = activeThreads->begin();
407 list<ThreadID>::iterator end = activeThreads->end();
409 while (threads != end) {
410 ThreadID tid = *threads++;
412 if (instList[tid].empty())
416 head = instList[tid].begin();
417 lowest_num = (*head)->seqNum;
422 InstIt head_thread = instList[tid].begin();
424 DynInstPtr head_inst = (*head_thread);
426 assert(head_inst != 0);
428 if (head_inst->seqNum < lowest_num) {
430 lowest_num = head_inst->seqNum;
435 head = instList[0].end();
440 template <class Impl>
442 ROB<Impl>::updateTail()
444 tail = instList[0].end();
445 bool first_valid = true;
447 list<ThreadID>::iterator threads = activeThreads->begin();
448 list<ThreadID>::iterator end = activeThreads->end();
450 while (threads != end) {
451 ThreadID tid = *threads++;
453 if (instList[tid].empty()) {
457 // If this is the first valid then assign w/out
460 tail = instList[tid].end();
466 // Assign new tail if this thread's tail is younger
467 // than our current "tail high"
468 InstIt tail_thread = instList[tid].end();
471 if ((*tail_thread)->seqNum > (*tail)->seqNum) {
478 template <class Impl>
480 ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid)
483 DPRINTF(ROB, "Does not need to squash due to being empty "
490 DPRINTF(ROB, "Starting to squash within the ROB.\n");
492 robStatus[tid] = ROBSquashing;
494 doneSquashing[tid] = false;
496 squashedSeqNum[tid] = squash_num;
498 if (!instList[tid].empty()) {
499 InstIt tail_thread = instList[tid].end();
502 squashIt[tid] = tail_thread;
508 template <class Impl>
509 typename Impl::DynInstPtr
510 ROB<Impl>::readHeadInst(ThreadID tid)
512 if (threadEntries[tid] != 0) {
513 InstIt head_thread = instList[tid].begin();
515 assert((*head_thread)->isInROB()==true);
523 template <class Impl>
524 typename Impl::DynInstPtr
525 ROB<Impl>::readTailInst(ThreadID tid)
527 InstIt tail_thread = instList[tid].end();
533 template <class Impl>
535 ROB<Impl>::regStats()
537 using namespace Stats;
539 .name(name() + ".rob_reads")
540 .desc("The number of ROB reads");
543 .name(name() + ".rob_writes")
544 .desc("The number of ROB writes");
547 template <class Impl>
548 typename Impl::DynInstPtr
549 ROB<Impl>::findInst(ThreadID tid, InstSeqNum squash_inst)
551 for (InstIt it = instList[tid].begin(); it != instList[tid].end(); it++) {
552 if ((*it)->seqNum == squash_inst) {