rob_impl.hh revision 8822:e7ae13867098 
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 "cpu/o3/rob.hh"
35#include "debug/Fetch.hh"
36#include "debug/ROB.hh"
37
38using namespace std;
39
40template <class Impl>
41ROB<Impl>::ROB(O3CPU *_cpu, unsigned _numEntries, unsigned _squashWidth,
42               std::string _smtROBPolicy, unsigned _smtROBThreshold,
43               ThreadID _numThreads)
44    : cpu(_cpu),
45      numEntries(_numEntries),
46      squashWidth(_squashWidth),
47      numInstsInROB(0),
48      numThreads(_numThreads)
49{
50    for (ThreadID tid = 0; tid  < numThreads; tid++) {
51        squashedSeqNum[tid] = 0;
52        doneSquashing[tid] = true;
53        threadEntries[tid] = 0;
54    }
55
56    std::string policy = _smtROBPolicy;
57
58    //Convert string to lowercase
59    std::transform(policy.begin(), policy.end(), policy.begin(),
60                   (int(*)(int)) tolower);
61
62    //Figure out rob policy
63    if (policy == "dynamic") {
64        robPolicy = Dynamic;
65
66        //Set Max Entries to Total ROB Capacity
67        for (ThreadID tid = 0; tid < numThreads; tid++) {
68            maxEntries[tid] = numEntries;
69        }
70
71    } else if (policy == "partitioned") {
72        robPolicy = Partitioned;
73        DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");
74
75        //@todo:make work if part_amt doesnt divide evenly.
76        int part_amt = numEntries / numThreads;
77
78        //Divide ROB up evenly
79        for (ThreadID tid = 0; tid < numThreads; tid++) {
80            maxEntries[tid] = part_amt;
81        }
82
83    } else if (policy == "threshold") {
84        robPolicy = Threshold;
85        DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");
86
87        int threshold =  _smtROBThreshold;;
88
89        //Divide up by threshold amount
90        for (ThreadID tid = 0; tid < numThreads; tid++) {
91            maxEntries[tid] = threshold;
92        }
93    } else {
94        assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic,"
95                    "Partitioned, Threshold}");
96    }
97
98    // Set the per-thread iterators to the end of the instruction list.
99    for (ThreadID tid = 0; tid < numThreads; tid++) {
100        squashIt[tid] = instList[tid].end();
101    }
102
103    // Initialize the "universal" ROB head & tail point to invalid
104    // pointers
105    head = instList[0].end();
106    tail = instList[0].end();
107}
108
109template <class Impl>
110std::string
111ROB<Impl>::name() const
112{
113    return cpu->name() + ".rob";
114}
115
116template <class Impl>
117void
118ROB<Impl>::setActiveThreads(list<ThreadID> *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 (ThreadID tid = 0; tid < numThreads; tid++) {
129        instList[tid].clear();
130    }
131}
132
133template <class Impl>
134void
135ROB<Impl>::takeOverFrom()
136{
137    for (ThreadID 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<ThreadID>::iterator threads = activeThreads->begin();
158        list<ThreadID>::iterator end = activeThreads->end();
159
160        while (threads != end) {
161            ThreadID tid = *threads++;
162
163            if (robPolicy == Partitioned) {
164                maxEntries[tid] = numEntries / active_threads;
165            } else if (robPolicy == Threshold && active_threads == 1) {
166                maxEntries[tid] = numEntries;
167            }
168        }
169    }
170}
171
172template <class Impl>
173int
174ROB<Impl>::entryAmount(ThreadID 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 (ThreadID tid = 0; tid < numThreads; tid++)
190        total += countInsts(tid);
191
192    return total;
193}
194
195template <class Impl>
196int
197ROB<Impl>::countInsts(ThreadID tid)
198{
199    return instList[tid].size();
200}
201
202template <class Impl>
203void
204ROB<Impl>::insertInst(DynInstPtr &inst)
205{
206    assert(inst);
207
208    robWrites++;
209
210    DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState());
211
212    assert(numInstsInROB != numEntries);
213
214    ThreadID tid = inst->threadNumber;
215
216    instList[tid].push_back(inst);
217
218    //Set Up head iterator if this is the 1st instruction in the ROB
219    if (numInstsInROB == 0) {
220        head = instList[tid].begin();
221        assert((*head) == inst);
222    }
223
224    //Must Decrement for iterator to actually be valid  since __.end()
225    //actually points to 1 after the last inst
226    tail = instList[tid].end();
227    tail--;
228
229    inst->setInROB();
230
231    ++numInstsInROB;
232    ++threadEntries[tid];
233
234    assert((*tail) == inst);
235
236    DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
237}
238
239template <class Impl>
240void
241ROB<Impl>::retireHead(ThreadID tid)
242{
243    robWrites++;
244
245    assert(numInstsInROB > 0);
246
247    // Get the head ROB instruction.
248    InstIt head_it = instList[tid].begin();
249
250    DynInstPtr head_inst = (*head_it);
251
252    assert(head_inst->readyToCommit());
253
254    DPRINTF(ROB, "[tid:%u]: Retiring head instruction, "
255            "instruction PC %s, [sn:%lli]\n", tid, head_inst->pcState(),
256            head_inst->seqNum);
257
258    --numInstsInROB;
259    --threadEntries[tid];
260
261    head_inst->clearInROB();
262    head_inst->setCommitted();
263
264    instList[tid].erase(head_it);
265
266    //Update "Global" Head of ROB
267    updateHead();
268
269    // @todo: A special case is needed if the instruction being
270    // retired is the only instruction in the ROB; otherwise the tail
271    // iterator will become invalidated.
272    cpu->removeFrontInst(head_inst);
273}
274
275template <class Impl>
276bool
277ROB<Impl>::isHeadReady(ThreadID tid)
278{
279    robReads++;
280    if (threadEntries[tid] != 0) {
281        return instList[tid].front()->readyToCommit();
282    }
283
284    return false;
285}
286
287template <class Impl>
288bool
289ROB<Impl>::canCommit()
290{
291    //@todo: set ActiveThreads through ROB or CPU
292    list<ThreadID>::iterator threads = activeThreads->begin();
293    list<ThreadID>::iterator end = activeThreads->end();
294
295    while (threads != end) {
296        ThreadID tid = *threads++;
297
298        if (isHeadReady(tid)) {
299            return true;
300        }
301    }
302
303    return false;
304}
305
306template <class Impl>
307unsigned
308ROB<Impl>::numFreeEntries()
309{
310    return numEntries - numInstsInROB;
311}
312
313template <class Impl>
314unsigned
315ROB<Impl>::numFreeEntries(ThreadID tid)
316{
317    return maxEntries[tid] - threadEntries[tid];
318}
319
320template <class Impl>
321void
322ROB<Impl>::doSquash(ThreadID tid)
323{
324    robWrites++;
325    DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n",
326            tid, squashedSeqNum[tid]);
327
328    assert(squashIt[tid] != instList[tid].end());
329
330    if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
331        DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
332                tid);
333
334        squashIt[tid] = instList[tid].end();
335
336        doneSquashing[tid] = true;
337        return;
338    }
339
340    bool robTailUpdate = false;
341
342    for (int numSquashed = 0;
343         numSquashed < squashWidth &&
344         squashIt[tid] != instList[tid].end() &&
345         (*squashIt[tid])->seqNum > squashedSeqNum[tid];
346         ++numSquashed)
347    {
348        DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %s, seq num %i.\n",
349                (*squashIt[tid])->threadNumber,
350                (*squashIt[tid])->pcState(),
351                (*squashIt[tid])->seqNum);
352
353        // Mark the instruction as squashed, and ready to commit so that
354        // it can drain out of the pipeline.
355        (*squashIt[tid])->setSquashed();
356
357        (*squashIt[tid])->setCanCommit();
358
359
360        if (squashIt[tid] == instList[tid].begin()) {
361            DPRINTF(ROB, "Reached head of instruction list while "
362                    "squashing.\n");
363
364            squashIt[tid] = instList[tid].end();
365
366            doneSquashing[tid] = true;
367
368            return;
369        }
370
371        InstIt tail_thread = instList[tid].end();
372        tail_thread--;
373
374        if ((*squashIt[tid]) == (*tail_thread))
375            robTailUpdate = true;
376
377        squashIt[tid]--;
378    }
379
380
381    // Check if ROB is done squashing.
382    if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
383        DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
384                tid);
385
386        squashIt[tid] = instList[tid].end();
387
388        doneSquashing[tid] = true;
389    }
390
391    if (robTailUpdate) {
392        updateTail();
393    }
394}
395
396
397template <class Impl>
398void
399ROB<Impl>::updateHead()
400{
401    DynInstPtr head_inst;
402    InstSeqNum lowest_num = 0;
403    bool first_valid = true;
404
405    // @todo: set ActiveThreads through ROB or CPU
406    list<ThreadID>::iterator threads = activeThreads->begin();
407    list<ThreadID>::iterator end = activeThreads->end();
408
409    while (threads != end) {
410        ThreadID tid = *threads++;
411
412        if (instList[tid].empty())
413            continue;
414
415        if (first_valid) {
416            head = instList[tid].begin();
417            lowest_num = (*head)->seqNum;
418            first_valid = false;
419            continue;
420        }
421
422        InstIt head_thread = instList[tid].begin();
423
424        DynInstPtr head_inst = (*head_thread);
425
426        assert(head_inst != 0);
427
428        if (head_inst->seqNum < lowest_num) {
429            head = head_thread;
430            lowest_num = head_inst->seqNum;
431        }
432    }
433
434    if (first_valid) {
435        head = instList[0].end();
436    }
437
438}
439
440template <class Impl>
441void
442ROB<Impl>::updateTail()
443{
444    tail = instList[0].end();
445    bool first_valid = true;
446
447    list<ThreadID>::iterator threads = activeThreads->begin();
448    list<ThreadID>::iterator end = activeThreads->end();
449
450    while (threads != end) {
451        ThreadID tid = *threads++;
452
453        if (instList[tid].empty()) {
454            continue;
455        }
456
457        // If this is the first valid then assign w/out
458        // comparison
459        if (first_valid) {
460            tail = instList[tid].end();
461            tail--;
462            first_valid = false;
463            continue;
464        }
465
466        // Assign new tail if this thread's tail is younger
467        // than our current "tail high"
468        InstIt tail_thread = instList[tid].end();
469        tail_thread--;
470
471        if ((*tail_thread)->seqNum > (*tail)->seqNum) {
472            tail = tail_thread;
473        }
474    }
475}
476
477
478template <class Impl>
479void
480ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid)
481{
482    if (isEmpty()) {
483        DPRINTF(ROB, "Does not need to squash due to being empty "
484                "[sn:%i]\n",
485                squash_num);
486
487        return;
488    }
489
490    DPRINTF(ROB, "Starting to squash within the ROB.\n");
491
492    robStatus[tid] = ROBSquashing;
493
494    doneSquashing[tid] = false;
495
496    squashedSeqNum[tid] = squash_num;
497
498    if (!instList[tid].empty()) {
499        InstIt tail_thread = instList[tid].end();
500        tail_thread--;
501
502        squashIt[tid] = tail_thread;
503
504        doSquash(tid);
505    }
506}
507
508template <class Impl>
509typename Impl::DynInstPtr
510ROB<Impl>::readHeadInst(ThreadID tid)
511{
512    if (threadEntries[tid] != 0) {
513        InstIt head_thread = instList[tid].begin();
514
515        assert((*head_thread)->isInROB()==true);
516
517        return *head_thread;
518    } else {
519        return dummyInst;
520    }
521}
522
523template <class Impl>
524typename Impl::DynInstPtr
525ROB<Impl>::readTailInst(ThreadID tid)
526{
527    InstIt tail_thread = instList[tid].end();
528    tail_thread--;
529
530    return *tail_thread;
531}
532
533template <class Impl>
534void
535ROB<Impl>::regStats()
536{
537    using namespace Stats;
538    robReads
539        .name(name() + ".rob_reads")
540        .desc("The number of ROB reads");
541
542    robWrites
543        .name(name() + ".rob_writes")
544        .desc("The number of ROB writes");
545}
546
547template <class Impl>
548typename Impl::DynInstPtr
549ROB<Impl>::findInst(ThreadID tid, InstSeqNum squash_inst)
550{
551    for (InstIt it = instList[tid].begin(); it != instList[tid].end(); it++) {
552        if ((*it)->seqNum == squash_inst) {
553            return *it;
554        }
555    }
556    return NULL;
557}
558