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