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