rob_impl.hh revision 7720:65d338a8dba4
1892SN/A/*
21762SN/A * Copyright (c) 2004-2006 The Regents of The University of Michigan
3892SN/A * All rights reserved.
4892SN/A *
5892SN/A * Redistribution and use in source and binary forms, with or without
6892SN/A * modification, are permitted provided that the following conditions are
7892SN/A * met: redistributions of source code must retain the above copyright
8892SN/A * notice, this list of conditions and the following disclaimer;
9892SN/A * redistributions in binary form must reproduce the above copyright
10892SN/A * notice, this list of conditions and the following disclaimer in the
11892SN/A * documentation and/or other materials provided with the distribution;
12892SN/A * neither the name of the copyright holders nor the names of its
13892SN/A * contributors may be used to endorse or promote products derived from
14892SN/A * this software without specific prior written permission.
15892SN/A *
16892SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17892SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18892SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19892SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20892SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21892SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22892SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23892SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24892SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25892SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26892SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
272665SN/A *
282665SN/A * Authors: Kevin Lim
292665SN/A *          Korey Sewell
30892SN/A */
31768SN/A
321730SN/A#include <list>
33768SN/A
34768SN/A#include "config/full_system.hh"
35768SN/A#include "cpu/o3/rob.hh"
36768SN/A
37768SN/Ausing namespace std;
38768SN/A
39768SN/Atemplate <class Impl>
40768SN/AROB<Impl>::ROB(O3CPU *_cpu, unsigned _numEntries, unsigned _squashWidth,
413540Sgblack@eecs.umich.edu               std::string _smtROBPolicy, unsigned _smtROBThreshold,
423540Sgblack@eecs.umich.edu               ThreadID _numThreads)
433540Sgblack@eecs.umich.edu    : cpu(_cpu),
442542SN/A      numEntries(_numEntries),
453348SN/A      squashWidth(_squashWidth),
46768SN/A      numInstsInROB(0),
47768SN/A      numThreads(_numThreads)
48768SN/A{
49768SN/A    for (ThreadID tid = 0; tid  < numThreads; tid++) {
502107SN/A        squashedSeqNum[tid] = 0;
512107SN/A        doneSquashing[tid] = true;
52768SN/A        threadEntries[tid] = 0;
532539SN/A    }
542542SN/A
55768SN/A    std::string policy = _smtROBPolicy;
562539SN/A
57809SN/A    //Convert string to lowercase
58835SN/A    std::transform(policy.begin(), policy.end(), policy.begin(),
59835SN/A                   (int(*)(int)) tolower);
60835SN/A
61835SN/A    //Figure out rob policy
62835SN/A    if (policy == "dynamic") {
63768SN/A        robPolicy = Dynamic;
64896SN/A
65896SN/A        //Set Max Entries to Total ROB Capacity
66896SN/A        for (ThreadID tid = 0; tid < numThreads; tid++) {
67775SN/A            maxEntries[tid] = numEntries;
682539SN/A        }
692539SN/A
702539SN/A    } else if (policy == "partitioned") {
712539SN/A        robPolicy = Partitioned;
723349SN/A        DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");
732539SN/A
742641SN/A        //@todo:make work if part_amt doesnt divide evenly.
752641SN/A        int part_amt = numEntries / numThreads;
762539SN/A
772630SN/A        //Divide ROB up evenly
782641SN/A        for (ThreadID tid = 0; tid < numThreads; tid++) {
792641SN/A            maxEntries[tid] = part_amt;
802539SN/A        }
812539SN/A
822641SN/A    } else if (policy == "threshold") {
832539SN/A        robPolicy = Threshold;
842539SN/A        DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");
852539SN/A
862630SN/A        int threshold =  _smtROBThreshold;;
872539SN/A
882539SN/A        //Divide up by threshold amount
892630SN/A        for (ThreadID tid = 0; tid < numThreads; tid++) {
902539SN/A            maxEntries[tid] = threshold;
912539SN/A        }
922630SN/A    } else {
932539SN/A        assert(0 && "Invalid ROB Sharing Policy.Options Are:{Dynamic,"
942539SN/A                    "Partitioned, Threshold}");
952630SN/A    }
962539SN/A
972539SN/A    // Set the per-thread iterators to the end of the instruction list.
982630SN/A    for (ThreadID tid = 0; tid < numThreads; tid++) {
992539SN/A        squashIt[tid] = instList[tid].end();
1002539SN/A    }
1012630SN/A
1022539SN/A    // Initialize the "universal" ROB head & tail point to invalid
1032539SN/A    // pointers
1042630SN/A    head = instList[0].end();
1052539SN/A    tail = instList[0].end();
1062539SN/A}
1072630SN/A
1082539SN/Atemplate <class Impl>
1092539SN/Astd::string
1102630SN/AROB<Impl>::name() const
1112539SN/A{
1122539SN/A    return cpu->name() + ".rob";
1132630SN/A}
1142539SN/A
1152539SN/Atemplate <class Impl>
1162630SN/Avoid
1172539SN/AROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr)
1182542SN/A{
1192630SN/A    DPRINTF(ROB, "Setting active threads list pointer.\n");
1202539SN/A    activeThreads = at_ptr;
1212539SN/A}
1222630SN/A
1232539SN/Atemplate <class Impl>
1242539SN/Avoid
1252539SN/AROB<Impl>::switchOut()
1262539SN/A{
1272539SN/A    for (ThreadID tid = 0; tid < numThreads; tid++) {
1282539SN/A        instList[tid].clear();
1292630SN/A    }
1302539SN/A}
1312539SN/A
1322630SN/Atemplate <class Impl>
1332539SN/Avoid
1342539SN/AROB<Impl>::takeOverFrom()
1352539SN/A{
1362539SN/A    for (ThreadID tid = 0; tid  < numThreads; tid++) {
1372539SN/A        doneSquashing[tid] = true;
1382539SN/A        threadEntries[tid] = 0;
1392630SN/A        squashIt[tid] = instList[tid].end();
1402539SN/A    }
1412539SN/A    numInstsInROB = 0;
1422539SN/A
1432539SN/A    // Initialize the "universal" ROB head & tail point to invalid
1442539SN/A    // pointers
1452539SN/A    head = instList[0].end();
1462539SN/A    tail = instList[0].end();
1472539SN/A}
1482641SN/A
1492539SN/Atemplate <class Impl>
1502539SN/Avoid
151768SN/AROB<Impl>::resetEntries()
152768SN/A{
1532542SN/A    if (robPolicy != Dynamic || numThreads > 1) {
1543349SN/A        int active_threads = activeThreads->size();
155768SN/A
1562641SN/A        list<ThreadID>::iterator threads = activeThreads->begin();
1572641SN/A        list<ThreadID>::iterator end = activeThreads->end();
1582641SN/A
159768SN/A        while (threads != end) {
1602641SN/A            ThreadID tid = *threads++;
161768SN/A
1622641SN/A            if (robPolicy == Partitioned) {
163768SN/A                maxEntries[tid] = numEntries / active_threads;
1642539SN/A            } else if (robPolicy == Threshold && active_threads == 1) {
1652539SN/A                maxEntries[tid] = numEntries;
1662630SN/A            }
1672539SN/A        }
1682539SN/A    }
1692630SN/A}
1702539SN/A
1712539SN/Atemplate <class Impl>
1722630SN/Aint
1732539SN/AROB<Impl>::entryAmount(ThreadID num_threads)
1742539SN/A{
1752630SN/A    if (robPolicy == Partitioned) {
1762539SN/A        return numEntries / num_threads;
1772539SN/A    } else {
1782630SN/A        return 0;
1792539SN/A    }
1802539SN/A}
1812630SN/A
1822539SN/Atemplate <class Impl>
1832539SN/Aint
1842630SN/AROB<Impl>::countInsts()
1852539SN/A{
1862539SN/A    int total = 0;
1872630SN/A
1882539SN/A    for (ThreadID tid = 0; tid < numThreads; tid++)
1892539SN/A        total += countInsts(tid);
1902630SN/A
1912539SN/A    return total;
1922539SN/A}
1932630SN/A
1942539SN/Atemplate <class Impl>
1952539SN/Aint
1962630SN/AROB<Impl>::countInsts(ThreadID tid)
1972539SN/A{
1982539SN/A    return instList[tid].size();
1992630SN/A}
2002539SN/A
2012539SN/Atemplate <class Impl>
2022630SN/Avoid
2032539SN/AROB<Impl>::insertInst(DynInstPtr &inst)
2042539SN/A{
2052539SN/A    assert(inst);
2062539SN/A
2072539SN/A    DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState());
2082539SN/A
2092539SN/A    assert(numInstsInROB != numEntries);
2102539SN/A
2112539SN/A    ThreadID tid = inst->threadNumber;
2122539SN/A
2132539SN/A    instList[tid].push_back(inst);
2142539SN/A
2152539SN/A    //Set Up head iterator if this is the 1st instruction in the ROB
2162539SN/A    if (numInstsInROB == 0) {
2172539SN/A        head = instList[tid].begin();
2182539SN/A        assert((*head) == inst);
2192539SN/A    }
2202539SN/A
2212539SN/A    //Must Decrement for iterator to actually be valid  since __.end()
2222539SN/A    //actually points to 1 after the last inst
2232549SN/A    tail = instList[tid].end();
224768SN/A    tail--;
2252539SN/A
226768SN/A    inst->setInROB();
2272641SN/A
2282539SN/A    ++numInstsInROB;
229768SN/A    ++threadEntries[tid];
230768SN/A
231857SN/A    assert((*tail) == inst);
232857SN/A
233835SN/A    DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
234835SN/A}
235835SN/A
236835SN/Atemplate <class Impl>
237857SN/Avoid
238857SN/AROB<Impl>::retireHead(ThreadID tid)
239857SN/A{
240835SN/A    assert(numInstsInROB > 0);
241835SN/A
242857SN/A    // Get the head ROB instruction.
243857SN/A    InstIt head_it = instList[tid].begin();
244857SN/A
245857SN/A    DynInstPtr head_inst = (*head_it);
246835SN/A
247835SN/A    assert(head_inst->readyToCommit());
248896SN/A
249896SN/A    DPRINTF(ROB, "[tid:%u]: Retiring head instruction, "
250835SN/A            "instruction PC %s, [sn:%lli]\n", tid, head_inst->pcState(),
251896SN/A            head_inst->seqNum);
252896SN/A
253896SN/A    --numInstsInROB;
254835SN/A    --threadEntries[tid];
255896SN/A
256835SN/A    head_inst->clearInROB();
257835SN/A    head_inst->setCommitted();
258896SN/A
259896SN/A    instList[tid].erase(head_it);
260896SN/A
261896SN/A    //Update "Global" Head of ROB
262896SN/A    updateHead();
263896SN/A
264857SN/A    // @todo: A special case is needed if the instruction being
265896SN/A    // retired is the only instruction in the ROB; otherwise the tail
266896SN/A    // iterator will become invalidated.
267896SN/A    cpu->removeFrontInst(head_inst);
268896SN/A}
269896SN/A
270896SN/Atemplate <class Impl>
271835SN/Abool
272835SN/AROB<Impl>::isHeadReady(ThreadID tid)
273857SN/A{
274857SN/A    if (threadEntries[tid] != 0) {
275857SN/A        return instList[tid].front()->readyToCommit();
276857SN/A    }
277857SN/A
278857SN/A    return false;
279857SN/A}
280857SN/A
281857SN/Atemplate <class Impl>
282857SN/Abool
283835SN/AROB<Impl>::canCommit()
284896SN/A{
285896SN/A    //@todo: set ActiveThreads through ROB or CPU
286857SN/A    list<ThreadID>::iterator threads = activeThreads->begin();
287857SN/A    list<ThreadID>::iterator end = activeThreads->end();
2882542SN/A
289857SN/A    while (threads != end) {
290896SN/A        ThreadID tid = *threads++;
291857SN/A
292857SN/A        if (isHeadReady(tid)) {
293896SN/A            return true;
294857SN/A        }
295857SN/A    }
296857SN/A
297857SN/A    return false;
298857SN/A}
299835SN/A
300835SN/Atemplate <class Impl>
301835SN/Aunsigned
302835SN/AROB<Impl>::numFreeEntries()
303896SN/A{
304896SN/A    return numEntries - numInstsInROB;
305835SN/A}
3062846SN/A
3072846SN/Atemplate <class Impl>
3082846SN/Aunsigned
3092846SN/AROB<Impl>::numFreeEntries(ThreadID tid)
3102846SN/A{
3112846SN/A    return maxEntries[tid] - threadEntries[tid];
3122846SN/A}
3132846SN/A
3142846SN/Atemplate <class Impl>
3152846SN/Avoid
3162846SN/AROB<Impl>::doSquash(ThreadID tid)
317835SN/A{
318768SN/A    DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n",
319768SN/A            tid, squashedSeqNum[tid]);
320768SN/A
321896SN/A    assert(squashIt[tid] != instList[tid].end());
322835SN/A
323835SN/A    if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
324835SN/A        DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
325768SN/A                tid);
326768SN/A
327768SN/A        squashIt[tid] = instList[tid].end();
328768SN/A
329768SN/A        doneSquashing[tid] = true;
330896SN/A        return;
331835SN/A    }
332835SN/A
333835SN/A    bool robTailUpdate = false;
334768SN/A
335768SN/A    for (int numSquashed = 0;
336909SN/A         numSquashed < squashWidth &&
337768SN/A         squashIt[tid] != instList[tid].end() &&
338768SN/A         (*squashIt[tid])->seqNum > squashedSeqNum[tid];
3392539SN/A         ++numSquashed)
3402539SN/A    {
3412539SN/A        DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %s, seq num %i.\n",
3422539SN/A                (*squashIt[tid])->threadNumber,
343775SN/A                (*squashIt[tid])->pcState(),
344768SN/A                (*squashIt[tid])->seqNum);
345768SN/A
346768SN/A        // Mark the instruction as squashed, and ready to commit so that
347768SN/A        // it can drain out of the pipeline.
348768SN/A        (*squashIt[tid])->setSquashed();
3492539SN/A
3502539SN/A        (*squashIt[tid])->setCanCommit();
3512539SN/A
3522539SN/A
3532539SN/A        if (squashIt[tid] == instList[tid].begin()) {
354768SN/A            DPRINTF(ROB, "Reached head of instruction list while "
355768SN/A                    "squashing.\n");
356768SN/A
357768SN/A            squashIt[tid] = instList[tid].end();
358768SN/A
3592539SN/A            doneSquashing[tid] = true;
3602539SN/A
3612539SN/A            return;
3622539SN/A        }
3632539SN/A
3642539SN/A        InstIt tail_thread = instList[tid].end();
3652539SN/A        tail_thread--;
3662539SN/A
367768SN/A        if ((*squashIt[tid]) == (*tail_thread))
368768SN/A            robTailUpdate = true;
369768SN/A
370        squashIt[tid]--;
371    }
372
373
374    // Check if ROB is done squashing.
375    if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
376        DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
377                tid);
378
379        squashIt[tid] = instList[tid].end();
380
381        doneSquashing[tid] = true;
382    }
383
384    if (robTailUpdate) {
385        updateTail();
386    }
387}
388
389
390template <class Impl>
391void
392ROB<Impl>::updateHead()
393{
394    DynInstPtr head_inst;
395    InstSeqNum lowest_num = 0;
396    bool first_valid = true;
397
398    // @todo: set ActiveThreads through ROB or CPU
399    list<ThreadID>::iterator threads = activeThreads->begin();
400    list<ThreadID>::iterator end = activeThreads->end();
401
402    while (threads != end) {
403        ThreadID tid = *threads++;
404
405        if (instList[tid].empty())
406            continue;
407
408        if (first_valid) {
409            head = instList[tid].begin();
410            lowest_num = (*head)->seqNum;
411            first_valid = false;
412            continue;
413        }
414
415        InstIt head_thread = instList[tid].begin();
416
417        DynInstPtr head_inst = (*head_thread);
418
419        assert(head_inst != 0);
420
421        if (head_inst->seqNum < lowest_num) {
422            head = head_thread;
423            lowest_num = head_inst->seqNum;
424        }
425    }
426
427    if (first_valid) {
428        head = instList[0].end();
429    }
430
431}
432
433template <class Impl>
434void
435ROB<Impl>::updateTail()
436{
437    tail = instList[0].end();
438    bool first_valid = true;
439
440    list<ThreadID>::iterator threads = activeThreads->begin();
441    list<ThreadID>::iterator end = activeThreads->end();
442
443    while (threads != end) {
444        ThreadID tid = *threads++;
445
446        if (instList[tid].empty()) {
447            continue;
448        }
449
450        // If this is the first valid then assign w/out
451        // comparison
452        if (first_valid) {
453            tail = instList[tid].end();
454            tail--;
455            first_valid = false;
456            continue;
457        }
458
459        // Assign new tail if this thread's tail is younger
460        // than our current "tail high"
461        InstIt tail_thread = instList[tid].end();
462        tail_thread--;
463
464        if ((*tail_thread)->seqNum > (*tail)->seqNum) {
465            tail = tail_thread;
466        }
467    }
468}
469
470
471template <class Impl>
472void
473ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid)
474{
475    if (isEmpty()) {
476        DPRINTF(ROB, "Does not need to squash due to being empty "
477                "[sn:%i]\n",
478                squash_num);
479
480        return;
481    }
482
483    DPRINTF(ROB, "Starting to squash within the ROB.\n");
484
485    robStatus[tid] = ROBSquashing;
486
487    doneSquashing[tid] = false;
488
489    squashedSeqNum[tid] = squash_num;
490
491    if (!instList[tid].empty()) {
492        InstIt tail_thread = instList[tid].end();
493        tail_thread--;
494
495        squashIt[tid] = tail_thread;
496
497        doSquash(tid);
498    }
499}
500
501template <class Impl>
502typename Impl::DynInstPtr
503ROB<Impl>::readHeadInst(ThreadID tid)
504{
505    if (threadEntries[tid] != 0) {
506        InstIt head_thread = instList[tid].begin();
507
508        assert((*head_thread)->isInROB()==true);
509
510        return *head_thread;
511    } else {
512        return dummyInst;
513    }
514}
515
516template <class Impl>
517typename Impl::DynInstPtr
518ROB<Impl>::readTailInst(ThreadID tid)
519{
520    InstIt tail_thread = instList[tid].end();
521    tail_thread--;
522
523    return *tail_thread;
524}
525
526