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