1/*
2 * Copyright (c) 2004-2006 The Regents of The University of Michigan
3 * All rights reserved.
4 *
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

--- 8 unchanged lines hidden (view full) ---

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.
27 */
28
29#include "config/full_system.hh"
30#include "cpu/o3/rob.hh"
31
32using namespace std;
33
34template <class Impl>
35ROB<Impl>::ROB(unsigned _numEntries, unsigned _squashWidth,
36 string _smtROBPolicy, unsigned _smtROBThreshold,
37 unsigned _numThreads)
38 : numEntries(_numEntries),
39 squashWidth(_squashWidth),
40 numInstsInROB(0),
41 squashedSeqNum(0),
42 numThreads(_numThreads)
43{
44 for (int tid=0; tid < numThreads; tid++) {
45 doneSquashing[tid] = true;
46 threadEntries[tid] = 0;
47 }
48
49 string policy = _smtROBPolicy;
50
51 //Convert string to lowercase
52 std::transform(policy.begin(), policy.end(), policy.begin(),
53 (int(*)(int)) tolower);
54
55 //Figure out rob policy
56 if (policy == "dynamic") {
57 robPolicy = Dynamic;
58
59 //Set Max Entries to Total ROB Capacity
60 for (int i = 0; i < numThreads; i++) {
61 maxEntries[i]=numEntries;
62 }
63
64 } else if (policy == "partitioned") {
65 robPolicy = Partitioned;
66 DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");
67
68 //@todo:make work if part_amt doesnt divide evenly.
69 int part_amt = numEntries / numThreads;
70
71 //Divide ROB up evenly
72 for (int i = 0; i < numThreads; i++) {
73 maxEntries[i]=part_amt;
74 }
75
76 } else if (policy == "threshold") {
77 robPolicy = Threshold;
78 DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");
79
80 int threshold = _smtROBThreshold;;
81
82 //Divide up by threshold amount
83 for (int i = 0; i < numThreads; i++) {
84 maxEntries[i]=threshold;
85 }
86 } else {
87 assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic,"
88 "Partitioned, Threshold}");
89 }
90}
91
92template <class Impl>
93std::string
94ROB<Impl>::name() const
95{
96 return cpu->name() + ".rob";
97}
98
99template <class Impl>
100void
101ROB<Impl>::setCPU(FullCPU *cpu_ptr)
102{
103 cpu = cpu_ptr;
104
105 // Set the per-thread iterators to the end of the instruction list.
106 for (int i=0; i < numThreads;i++) {
107 squashIt[i] = instList[i].end();
108 }
109
110 // Initialize the "universal" ROB head & tail point to invalid
111 // pointers
112 head = instList[0].end();
113 tail = instList[0].end();
114}
115
116template <class Impl>
117void
118ROB<Impl>::setActiveThreads(list<unsigned> *at_ptr)
119{
120 DPRINTF(ROB, "Setting active threads list pointer.\n");
121 activeThreads = at_ptr;
122}
123
124template <class Impl>
125void
126ROB<Impl>::switchOut()
127{
128 for (int tid = 0; tid < numThreads; tid++) {
129 instList[tid].clear();
130 }
131}
132
133template <class Impl>
134void
135ROB<Impl>::takeOverFrom()
136{
137 for (int tid=0; tid < numThreads; tid++) {
138 doneSquashing[tid] = true;
139 threadEntries[tid] = 0;
140 squashIt[tid] = instList[tid].end();
141 }
142 numInstsInROB = 0;
143
144 // Initialize the "universal" ROB head & tail point to invalid
145 // pointers
146 head = instList[0].end();
147 tail = instList[0].end();
148}
149
150template <class Impl>
151void
152ROB<Impl>::resetEntries()
153{
154 if (robPolicy != Dynamic || numThreads > 1) {
155 int active_threads = (*activeThreads).size();
156
157 list<unsigned>::iterator threads = (*activeThreads).begin();
158 list<unsigned>::iterator list_end = (*activeThreads).end();
159
160 while (threads != list_end) {
161 if (robPolicy == Partitioned) {
162 maxEntries[*threads++] = numEntries / active_threads;
163 } else if (robPolicy == Threshold && active_threads == 1) {
164 maxEntries[*threads++] = numEntries;
165 }
166 }
167 }
168}
169
170template <class Impl>
171int
172ROB<Impl>::entryAmount(int num_threads)
173{
174 if (robPolicy == Partitioned) {
175 return numEntries / num_threads;
176 } else {
177 return 0;
178 }
179}
180
181template <class Impl>
182int
183ROB<Impl>::countInsts()
184{
185 int total=0;
186
187 for (int i=0;i < numThreads;i++)
188 total += countInsts(i);
189
190 return total;
191}
192
193template <class Impl>
194int
195ROB<Impl>::countInsts(unsigned tid)
196{
197 return instList[tid].size();
198}
199
200template <class Impl>
201void
202ROB<Impl>::insertInst(DynInstPtr &inst)
203{
204 //assert(numInstsInROB == countInsts());
205 assert(inst);
206
207 DPRINTF(ROB, "Adding inst PC %#x to the ROB.\n", inst->readPC());
208
209 assert(numInstsInROB != numEntries);
210
211 int tid = inst->threadNumber;
212
213 instList[tid].push_back(inst);
214
215 //Set Up head iterator if this is the 1st instruction in the ROB
216 if (numInstsInROB == 0) {
217 head = instList[tid].begin();
218 assert((*head) == inst);
219 }
220
221 //Must Decrement for iterator to actually be valid since __.end()
222 //actually points to 1 after the last inst
223 tail = instList[tid].end();
224 tail--;
225
226 inst->setInROB();
227
228 ++numInstsInROB;
229 ++threadEntries[tid];
230
231 assert((*tail) == inst);
232
233 DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
234}
235
236// Whatever calls this function needs to ensure that it properly frees up
237// registers prior to this function.
238/*
239template <class Impl>
240void
241ROB<Impl>::retireHead()
242{
243 //assert(numInstsInROB == countInsts());
244 assert(numInstsInROB > 0);
245
246 int tid = (*head)->threadNumber;
247
248 retireHead(tid);
249
250 if (numInstsInROB == 0) {
251 tail = instList[tid].end();
252 }
253}
254*/
255
256template <class Impl>
257void
258ROB<Impl>::retireHead(unsigned tid)
259{
260 //assert(numInstsInROB == countInsts());
261 assert(numInstsInROB > 0);
262
263 // Get the head ROB instruction.
264 InstIt head_it = instList[tid].begin();
265
266 DynInstPtr head_inst = (*head_it);
267
268 assert(head_inst->readyToCommit());
269
270 DPRINTF(ROB, "[tid:%u]: Retiring head instruction, "
271 "instruction PC %#x,[sn:%lli]\n", tid, head_inst->readPC(),
272 head_inst->seqNum);
273
274 --numInstsInROB;
275 --threadEntries[tid];
276
277 head_inst->removeInROB();
278 head_inst->setCommitted();
279
280 instList[tid].erase(head_it);
281
282 //Update "Global" Head of ROB
283 updateHead();
284
285 // @todo: A special case is needed if the instruction being
286 // retired is the only instruction in the ROB; otherwise the tail
287 // iterator will become invalidated.
288 cpu->removeFrontInst(head_inst);
289}
290/*
291template <class Impl>
292bool
293ROB<Impl>::isHeadReady()
294{
295 if (numInstsInROB != 0) {
296 return (*head)->readyToCommit();
297 }
298
299 return false;
300}
301*/
302template <class Impl>
303bool
304ROB<Impl>::isHeadReady(unsigned tid)
305{
306 if (threadEntries[tid] != 0) {
307 return instList[tid].front()->readyToCommit();
308 }
309
310 return false;
311}
312
313template <class Impl>
314bool
315ROB<Impl>::canCommit()
316{
317 //@todo: set ActiveThreads through ROB or CPU
318 list<unsigned>::iterator threads = (*activeThreads).begin();
319
320 while (threads != (*activeThreads).end()) {
321 unsigned tid = *threads++;
322
323 if (isHeadReady(tid)) {
324 return true;
325 }
326 }
327
328 return false;
329}
330
331template <class Impl>
332unsigned
333ROB<Impl>::numFreeEntries()
334{
335 //assert(numInstsInROB == countInsts());
336
337 return numEntries - numInstsInROB;
338}
339
340template <class Impl>
341unsigned
342ROB<Impl>::numFreeEntries(unsigned tid)
343{
344 return maxEntries[tid] - threadEntries[tid];
345}
346
347template <class Impl>
348void
349ROB<Impl>::doSquash(unsigned tid)
350{
351 DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n",
352 tid, squashedSeqNum);
353
354 assert(squashIt[tid] != instList[tid].end());
355
356 if ((*squashIt[tid])->seqNum < squashedSeqNum) {
357 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
358 tid);
359
360 squashIt[tid] = instList[tid].end();
361
362 doneSquashing[tid] = true;
363 return;
364 }
365
366 bool robTailUpdate = false;
367
368 for (int numSquashed = 0;
369 numSquashed < squashWidth &&
370 squashIt[tid] != instList[tid].end() &&
371 (*squashIt[tid])->seqNum > squashedSeqNum;
372 ++numSquashed)
373 {
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);
378
379 // Mark the instruction as squashed, and ready to commit so that
380 // it can drain out of the pipeline.
381 (*squashIt[tid])->setSquashed();
382
383 (*squashIt[tid])->setCanCommit();
384
385
386 if (squashIt[tid] == instList[tid].begin()) {
387 DPRINTF(ROB, "Reached head of instruction list while "
388 "squashing.\n");
389
390 squashIt[tid] = instList[tid].end();
391
392 doneSquashing[tid] = true;
393
394 return;
395 }
396
397 InstIt tail_thread = instList[tid].end();
398 tail_thread--;
399
400 if ((*squashIt[tid]) == (*tail_thread))
401 robTailUpdate = true;
402
403 squashIt[tid]--;
404 }
405
406
407 // Check if ROB is done squashing.
408 if ((*squashIt[tid])->seqNum <= squashedSeqNum) {
409 DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
410 tid);
411
412 squashIt[tid] = instList[tid].end();
413
414 doneSquashing[tid] = true;
415 }
416
417 if (robTailUpdate) {
418 updateTail();
419 }
420}
421
422
423template <class Impl>
424void
425ROB<Impl>::updateHead()
426{
427 DynInstPtr head_inst;
428 InstSeqNum lowest_num = 0;
429 bool first_valid = true;
430
431 // @todo: set ActiveThreads through ROB or CPU
432 list<unsigned>::iterator threads = (*activeThreads).begin();
433
434 while (threads != (*activeThreads).end()) {
435 unsigned thread_num = *threads++;
436
437 if (instList[thread_num].empty())
438 continue;
439
440 if (first_valid) {
441 head = instList[thread_num].begin();
442 lowest_num = (*head)->seqNum;
443 first_valid = false;
444 continue;
445 }
446
447 InstIt head_thread = instList[thread_num].begin();
448
449 DynInstPtr head_inst = (*head_thread);
450
451 assert(head_inst != 0);
452
453 if (head_inst->seqNum < lowest_num) {
454 head = head_thread;
455 lowest_num = head_inst->seqNum;
456 }
457 }
458
459 if (first_valid) {
460 head = instList[0].end();
461 }
462
463}
464
465template <class Impl>
466void
467ROB<Impl>::updateTail()
468{
469 tail = instList[0].end();
470 bool first_valid = true;
471
472 list<unsigned>::iterator threads = (*activeThreads).begin();
473
474 while (threads != (*activeThreads).end()) {
475 unsigned tid = *threads++;
476
477 if (instList[tid].empty()) {
478 continue;
479 }
480
481 // If this is the first valid then assign w/out
482 // comparison
483 if (first_valid) {
484 tail = instList[tid].end();
485 tail--;
486 first_valid = false;
487 continue;
488 }
489
490 // Assign new tail if this thread's tail is younger
491 // than our current "tail high"
492 InstIt tail_thread = instList[tid].end();
493 tail_thread--;
494
495 if ((*tail_thread)->seqNum > (*tail)->seqNum) {
496 tail = tail_thread;
497 }
498 }
499}
500
501
502template <class Impl>
503void
504ROB<Impl>::squash(InstSeqNum squash_num,unsigned tid)
505{
506 if (isEmpty()) {
507 DPRINTF(ROB, "Does not need to squash due to being empty "
508 "[sn:%i]\n",
509 squash_num);
510
511 return;
512 }
513
514 DPRINTF(ROB, "Starting to squash within the ROB.\n");
515
516 robStatus[tid] = ROBSquashing;
517
518 doneSquashing[tid] = false;
519
520 squashedSeqNum = squash_num;
521
522 if (!instList[tid].empty()) {
523 InstIt tail_thread = instList[tid].end();
524 tail_thread--;
525
526 squashIt[tid] = tail_thread;
527
528 doSquash(tid);
529 }
530}
531/*
532template <class Impl>
533typename Impl::DynInstPtr
534ROB<Impl>::readHeadInst()
535{
536 if (numInstsInROB != 0) {
537 assert((*head)->isInROB()==true);
538 return *head;
539 } else {
540 return dummyInst;
541 }
542}
543*/
544template <class Impl>
545typename Impl::DynInstPtr
546ROB<Impl>::readHeadInst(unsigned tid)
547{
548 if (threadEntries[tid] != 0) {
549 InstIt head_thread = instList[tid].begin();
550
551 assert((*head_thread)->isInROB()==true);
552
553 return *head_thread;
554 } else {
555 return dummyInst;
556 }
557}
558/*
559template <class Impl>
560uint64_t
561ROB<Impl>::readHeadPC()
562{
563 //assert(numInstsInROB == countInsts());
564
565 DynInstPtr head_inst = *head;
566
567 return head_inst->readPC();
568}
569
570template <class Impl>
571uint64_t
572ROB<Impl>::readHeadPC(unsigned tid)
573{
574 //assert(numInstsInROB == countInsts());
575 InstIt head_thread = instList[tid].begin();
576
577 return (*head_thread)->readPC();
578}
579
580
581template <class Impl>
582uint64_t
583ROB<Impl>::readHeadNextPC()
584{
585 //assert(numInstsInROB == countInsts());
586
587 DynInstPtr head_inst = *head;
588
589 return head_inst->readNextPC();
590}
591
592template <class Impl>
593uint64_t
594ROB<Impl>::readHeadNextPC(unsigned tid)
595{
596 //assert(numInstsInROB == countInsts());
597 InstIt head_thread = instList[tid].begin();
598
599 return (*head_thread)->readNextPC();
600}
601
602template <class Impl>
603InstSeqNum
604ROB<Impl>::readHeadSeqNum()
605{
606 //assert(numInstsInROB == countInsts());
607 DynInstPtr head_inst = *head;
608
609 return head_inst->seqNum;
610}
611
612template <class Impl>
613InstSeqNum
614ROB<Impl>::readHeadSeqNum(unsigned tid)
615{
616 InstIt head_thread = instList[tid].begin();
617
618 return ((*head_thread)->seqNum);
619}
620
621template <class Impl>
622typename Impl::DynInstPtr
623ROB<Impl>::readTailInst()
624{
625 //assert(numInstsInROB == countInsts());
626 //assert(tail != instList[0].end());
627
628 return (*tail);
629}
630*/
631template <class Impl>
632typename Impl::DynInstPtr
633ROB<Impl>::readTailInst(unsigned tid)
634{
635 //assert(tail_thread[tid] != instList[tid].end());
636
637 InstIt tail_thread = instList[tid].end();
638 tail_thread--;
639
640 return *tail_thread;
641}
642
643/*
644template <class Impl>
645uint64_t
646ROB<Impl>::readTailPC()
647{
648 //assert(numInstsInROB == countInsts());
649
650 //assert(tail != instList[0].end());
651
652 return (*tail)->readPC();
653}
654
655template <class Impl>
656uint64_t
657ROB<Impl>::readTailPC(unsigned tid)
658{
659 //assert(tail_thread[tid] != instList[tid].end());
660
661 InstIt tail_thread = instList[tid].end();
662 tail_thread--;
663
664 return (*tail_thread)->readPC();
665}
666
667template <class Impl>
668InstSeqNum
669ROB<Impl>::readTailSeqNum()
670{
671 // Return the last sequence number that has not been squashed. Other
672 // stages can use it to squash any instructions younger than the current
673 // tail.
674 return (*tail)->seqNum;
675}
676
677template <class Impl>
678InstSeqNum
679ROB<Impl>::readTailSeqNum(unsigned tid)
680{
681 // Return the last sequence number that has not been squashed. Other
682 // stages can use it to squash any instructions younger than the current
683 // tail.
684 // assert(tail_thread[tid] != instList[tid].end());
685
686 InstIt tail_thread = instList[tid].end();
687 tail_thread--;
688
689 return (*tail_thread)->seqNum;
690}
691*/