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