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