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