rob_impl.hh revision 2329
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
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*/
692