rob_impl.hh revision 2980
12817Sksewell@umich.edu/*
22817Sksewell@umich.edu * Copyright (c) 2004-2006 The Regents of The University of Michigan
32817Sksewell@umich.edu * All rights reserved.
42817Sksewell@umich.edu *
52817Sksewell@umich.edu * Redistribution and use in source and binary forms, with or without
62817Sksewell@umich.edu * modification, are permitted provided that the following conditions are
72817Sksewell@umich.edu * met: redistributions of source code must retain the above copyright
82817Sksewell@umich.edu * notice, this list of conditions and the following disclaimer;
92817Sksewell@umich.edu * redistributions in binary form must reproduce the above copyright
102817Sksewell@umich.edu * notice, this list of conditions and the following disclaimer in the
112817Sksewell@umich.edu * documentation and/or other materials provided with the distribution;
122817Sksewell@umich.edu * neither the name of the copyright holders nor the names of its
132817Sksewell@umich.edu * contributors may be used to endorse or promote products derived from
142817Sksewell@umich.edu * this software without specific prior written permission.
152817Sksewell@umich.edu *
162817Sksewell@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
172817Sksewell@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
182817Sksewell@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
192817Sksewell@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
202817Sksewell@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
212817Sksewell@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
222817Sksewell@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
232817Sksewell@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
242817Sksewell@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
252817Sksewell@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
262817Sksewell@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
272817Sksewell@umich.edu *
282817Sksewell@umich.edu * Authors: Kevin Lim
294202Sbinkertn@umich.edu *          Korey Sewell
302817Sksewell@umich.edu */
312817Sksewell@umich.edu
322817Sksewell@umich.edu#include "config/full_system.hh"
334202Sbinkertn@umich.edu#include "cpu/o3/rob.hh"
342817Sksewell@umich.edu
354202Sbinkertn@umich.edu#include <list>
364486Sbinkertn@umich.edu
374486Sbinkertn@umich.edutemplate <class Impl>
384486Sbinkertn@umich.eduROB<Impl>::ROB(unsigned _numEntries, unsigned _squashWidth,
394486Sbinkertn@umich.edu               std::string _smtROBPolicy, unsigned _smtROBThreshold,
404202Sbinkertn@umich.edu               unsigned _numThreads)
414202Sbinkertn@umich.edu    : numEntries(_numEntries),
424202Sbinkertn@umich.edu      squashWidth(_squashWidth),
439341SAndreas.Sandberg@arm.com      numInstsInROB(0),
444202Sbinkertn@umich.edu      numThreads(_numThreads)
455597Sgblack@eecs.umich.edu{
464202Sbinkertn@umich.edu    for (int tid=0; tid  < numThreads; tid++) {
474202Sbinkertn@umich.edu        squashedSeqNum[tid] = 0;
484202Sbinkertn@umich.edu        doneSquashing[tid] = true;
494202Sbinkertn@umich.edu        threadEntries[tid] = 0;
504202Sbinkertn@umich.edu    }
514202Sbinkertn@umich.edu
524202Sbinkertn@umich.edu    std::string policy = _smtROBPolicy;
534202Sbinkertn@umich.edu
549919Ssteve.reinhardt@amd.com    //Convert string to lowercase
554202Sbinkertn@umich.edu    std::transform(policy.begin(), policy.end(), policy.begin(),
564202Sbinkertn@umich.edu                   (int(*)(int)) tolower);
574202Sbinkertn@umich.edu
584202Sbinkertn@umich.edu    //Figure out rob policy
594202Sbinkertn@umich.edu    if (policy == "dynamic") {
605597Sgblack@eecs.umich.edu        robPolicy = Dynamic;
612817Sksewell@umich.edu
6210426Smitch.hayenga@arm.com        //Set Max Entries to Total ROB Capacity
6310426Smitch.hayenga@arm.com        for (int i = 0; i < numThreads; i++) {
6410426Smitch.hayenga@arm.com            maxEntries[i]=numEntries;
658335Snate@binkert.org        }
668335Snate@binkert.org
678335Snate@binkert.org    } else if (policy == "partitioned") {
688335Snate@binkert.org        robPolicy = Partitioned;
698335Snate@binkert.org        DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");
708335Snate@binkert.org
718335Snate@binkert.org        //@todo:make work if part_amt doesnt divide evenly.
728335Snate@binkert.org        int part_amt = numEntries / numThreads;
738335Snate@binkert.org
745192Ssaidi@eecs.umich.edu        //Divide ROB up evenly
755192Ssaidi@eecs.umich.edu        for (int i = 0; i < numThreads; i++) {
765192Ssaidi@eecs.umich.edu            maxEntries[i]=part_amt;
775192Ssaidi@eecs.umich.edu        }
785192Ssaidi@eecs.umich.edu
798887Sgeoffrey.blake@arm.com    } else if (policy == "threshold") {
809340SAndreas.Sandberg@arm.com        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 list_end = (*activeThreads).end();
162
163        while (threads != list_end) {
164            if (robPolicy == Partitioned) {
165                maxEntries[*threads++] = numEntries / active_threads;
166            } else if (robPolicy == Threshold && active_threads == 1) {
167                maxEntries[*threads++] = numEntries;
168            }
169        }
170    }
171}
172
173template <class Impl>
174int
175ROB<Impl>::entryAmount(int 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 (int i=0;i < numThreads;i++)
191        total += countInsts(i);
192
193    return total;
194}
195
196template <class Impl>
197int
198ROB<Impl>::countInsts(unsigned tid)
199{
200    return instList[tid].size();
201}
202
203template <class Impl>
204void
205ROB<Impl>::insertInst(DynInstPtr &inst)
206{
207    //assert(numInstsInROB == countInsts());
208    assert(inst);
209
210    DPRINTF(ROB, "Adding inst PC %#x to the ROB.\n", inst->readPC());
211
212    assert(numInstsInROB != numEntries);
213
214    int 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
239// Whatever calls this function needs to ensure that it properly frees up
240// registers prior to this function.
241/*
242template <class Impl>
243void
244ROB<Impl>::retireHead()
245{
246    //assert(numInstsInROB == countInsts());
247    assert(numInstsInROB > 0);
248
249    int tid = (*head)->threadNumber;
250
251    retireHead(tid);
252
253    if (numInstsInROB == 0) {
254        tail = instList[tid].end();
255    }
256}
257*/
258
259template <class Impl>
260void
261ROB<Impl>::retireHead(unsigned tid)
262{
263    //assert(numInstsInROB == countInsts());
264    assert(numInstsInROB > 0);
265
266    // Get the head ROB instruction.
267    InstIt head_it = instList[tid].begin();
268
269    DynInstPtr head_inst = (*head_it);
270
271    assert(head_inst->readyToCommit());
272
273    DPRINTF(ROB, "[tid:%u]: Retiring head instruction, "
274            "instruction PC %#x,[sn:%lli]\n", tid, head_inst->readPC(),
275            head_inst->seqNum);
276
277    --numInstsInROB;
278    --threadEntries[tid];
279
280    head_inst->clearInROB();
281    head_inst->setCommitted();
282
283    instList[tid].erase(head_it);
284
285    //Update "Global" Head of ROB
286    updateHead();
287
288    // @todo: A special case is needed if the instruction being
289    // retired is the only instruction in the ROB; otherwise the tail
290    // iterator will become invalidated.
291    cpu->removeFrontInst(head_inst);
292}
293/*
294template <class Impl>
295bool
296ROB<Impl>::isHeadReady()
297{
298    if (numInstsInROB != 0) {
299        return (*head)->readyToCommit();
300    }
301
302    return false;
303}
304*/
305template <class Impl>
306bool
307ROB<Impl>::isHeadReady(unsigned tid)
308{
309    if (threadEntries[tid] != 0) {
310        return instList[tid].front()->readyToCommit();
311    }
312
313    return false;
314}
315
316template <class Impl>
317bool
318ROB<Impl>::canCommit()
319{
320    //@todo: set ActiveThreads through ROB or CPU
321    std::list<unsigned>::iterator threads = (*activeThreads).begin();
322
323    while (threads != (*activeThreads).end()) {
324        unsigned tid = *threads++;
325
326        if (isHeadReady(tid)) {
327            return true;
328        }
329    }
330
331    return false;
332}
333
334template <class Impl>
335unsigned
336ROB<Impl>::numFreeEntries()
337{
338    //assert(numInstsInROB == countInsts());
339
340    return numEntries - numInstsInROB;
341}
342
343template <class Impl>
344unsigned
345ROB<Impl>::numFreeEntries(unsigned tid)
346{
347    return maxEntries[tid] - threadEntries[tid];
348}
349
350template <class Impl>
351void
352ROB<Impl>::doSquash(unsigned tid)
353{
354    DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n",
355            tid, squashedSeqNum[tid]);
356
357    assert(squashIt[tid] != instList[tid].end());
358
359    if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
360        DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
361                tid);
362
363        squashIt[tid] = instList[tid].end();
364
365        doneSquashing[tid] = true;
366        return;
367    }
368
369    bool robTailUpdate = false;
370
371    for (int numSquashed = 0;
372         numSquashed < squashWidth &&
373         squashIt[tid] != instList[tid].end() &&
374         (*squashIt[tid])->seqNum > squashedSeqNum[tid];
375         ++numSquashed)
376    {
377        DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %#x, seq num %i.\n",
378                (*squashIt[tid])->threadNumber,
379                (*squashIt[tid])->readPC(),
380                (*squashIt[tid])->seqNum);
381
382        // Mark the instruction as squashed, and ready to commit so that
383        // it can drain out of the pipeline.
384        (*squashIt[tid])->setSquashed();
385
386        (*squashIt[tid])->setCanCommit();
387
388
389        if (squashIt[tid] == instList[tid].begin()) {
390            DPRINTF(ROB, "Reached head of instruction list while "
391                    "squashing.\n");
392
393            squashIt[tid] = instList[tid].end();
394
395            doneSquashing[tid] = true;
396
397            return;
398        }
399
400        InstIt tail_thread = instList[tid].end();
401        tail_thread--;
402
403        if ((*squashIt[tid]) == (*tail_thread))
404            robTailUpdate = true;
405
406        squashIt[tid]--;
407    }
408
409
410    // Check if ROB is done squashing.
411    if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
412        DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
413                tid);
414
415        squashIt[tid] = instList[tid].end();
416
417        doneSquashing[tid] = true;
418    }
419
420    if (robTailUpdate) {
421        updateTail();
422    }
423}
424
425
426template <class Impl>
427void
428ROB<Impl>::updateHead()
429{
430    DynInstPtr head_inst;
431    InstSeqNum lowest_num = 0;
432    bool first_valid = true;
433
434    // @todo: set ActiveThreads through ROB or CPU
435    std::list<unsigned>::iterator threads = (*activeThreads).begin();
436
437    while (threads != (*activeThreads).end()) {
438        unsigned thread_num = *threads++;
439
440        if (instList[thread_num].empty())
441            continue;
442
443        if (first_valid) {
444            head = instList[thread_num].begin();
445            lowest_num = (*head)->seqNum;
446            first_valid = false;
447            continue;
448        }
449
450        InstIt head_thread = instList[thread_num].begin();
451
452        DynInstPtr head_inst = (*head_thread);
453
454        assert(head_inst != 0);
455
456        if (head_inst->seqNum < lowest_num) {
457            head = head_thread;
458            lowest_num = head_inst->seqNum;
459        }
460    }
461
462    if (first_valid) {
463        head = instList[0].end();
464    }
465
466}
467
468template <class Impl>
469void
470ROB<Impl>::updateTail()
471{
472    tail = instList[0].end();
473    bool first_valid = true;
474
475    std::list<unsigned>::iterator threads = (*activeThreads).begin();
476
477    while (threads != (*activeThreads).end()) {
478        unsigned tid = *threads++;
479
480        if (instList[tid].empty()) {
481            continue;
482        }
483
484        // If this is the first valid then assign w/out
485        // comparison
486        if (first_valid) {
487            tail = instList[tid].end();
488            tail--;
489            first_valid = false;
490            continue;
491        }
492
493        // Assign new tail if this thread's tail is younger
494        // than our current "tail high"
495        InstIt tail_thread = instList[tid].end();
496        tail_thread--;
497
498        if ((*tail_thread)->seqNum > (*tail)->seqNum) {
499            tail = tail_thread;
500        }
501    }
502}
503
504
505template <class Impl>
506void
507ROB<Impl>::squash(InstSeqNum squash_num,unsigned tid)
508{
509    if (isEmpty()) {
510        DPRINTF(ROB, "Does not need to squash due to being empty "
511                "[sn:%i]\n",
512                squash_num);
513
514        return;
515    }
516
517    DPRINTF(ROB, "Starting to squash within the ROB.\n");
518
519    robStatus[tid] = ROBSquashing;
520
521    doneSquashing[tid] = false;
522
523    squashedSeqNum[tid] = squash_num;
524
525    if (!instList[tid].empty()) {
526        InstIt tail_thread = instList[tid].end();
527        tail_thread--;
528
529        squashIt[tid] = tail_thread;
530
531        doSquash(tid);
532    }
533}
534/*
535template <class Impl>
536typename Impl::DynInstPtr
537ROB<Impl>::readHeadInst()
538{
539    if (numInstsInROB != 0) {
540        assert((*head)->isInROB()==true);
541        return *head;
542    } else {
543        return dummyInst;
544    }
545}
546*/
547
548template <class Impl>
549typename Impl::DynInstPtr
550ROB<Impl>::readHeadInst(unsigned tid)
551{
552    if (threadEntries[tid] != 0) {
553        InstIt head_thread = instList[tid].begin();
554
555        assert((*head_thread)->isInROB()==true);
556
557        return *head_thread;
558    } else {
559        return dummyInst;
560    }
561}
562
563/*
564template <class Impl>
565uint64_t
566ROB<Impl>::readHeadPC()
567{
568    //assert(numInstsInROB == countInsts());
569
570    DynInstPtr head_inst = *head;
571
572    return head_inst->readPC();
573}
574
575template <class Impl>
576uint64_t
577ROB<Impl>::readHeadPC(unsigned tid)
578{
579    //assert(numInstsInROB == countInsts());
580    InstIt head_thread = instList[tid].begin();
581
582    return (*head_thread)->readPC();
583}
584
585
586template <class Impl>
587uint64_t
588ROB<Impl>::readHeadNextPC()
589{
590    //assert(numInstsInROB == countInsts());
591
592    DynInstPtr head_inst = *head;
593
594    return head_inst->readNextPC();
595}
596
597template <class Impl>
598uint64_t
599ROB<Impl>::readHeadNextPC(unsigned tid)
600{
601    //assert(numInstsInROB == countInsts());
602    InstIt head_thread = instList[tid].begin();
603
604    return (*head_thread)->readNextPC();
605}
606
607template <class Impl>
608InstSeqNum
609ROB<Impl>::readHeadSeqNum()
610{
611    //assert(numInstsInROB == countInsts());
612    DynInstPtr head_inst = *head;
613
614    return head_inst->seqNum;
615}
616
617template <class Impl>
618InstSeqNum
619ROB<Impl>::readHeadSeqNum(unsigned tid)
620{
621    InstIt head_thread = instList[tid].begin();
622
623    return ((*head_thread)->seqNum);
624}
625
626template <class Impl>
627typename Impl::DynInstPtr
628ROB<Impl>::readTailInst()
629{
630    //assert(numInstsInROB == countInsts());
631    //assert(tail != instList[0].end());
632
633    return (*tail);
634}
635*/
636template <class Impl>
637typename Impl::DynInstPtr
638ROB<Impl>::readTailInst(unsigned tid)
639{
640    //assert(tail_thread[tid] != instList[tid].end());
641
642    InstIt tail_thread = instList[tid].end();
643    tail_thread--;
644
645    return *tail_thread;
646}
647
648/*
649template <class Impl>
650uint64_t
651ROB<Impl>::readTailPC()
652{
653    //assert(numInstsInROB == countInsts());
654
655    //assert(tail != instList[0].end());
656
657    return (*tail)->readPC();
658}
659
660template <class Impl>
661uint64_t
662ROB<Impl>::readTailPC(unsigned tid)
663{
664    //assert(tail_thread[tid] != instList[tid].end());
665
666    InstIt tail_thread = instList[tid].end();
667    tail_thread--;
668
669    return (*tail_thread)->readPC();
670}
671
672template <class Impl>
673InstSeqNum
674ROB<Impl>::readTailSeqNum()
675{
676    // Return the last sequence number that has not been squashed.  Other
677    // stages can use it to squash any instructions younger than the current
678    // tail.
679    return (*tail)->seqNum;
680}
681
682template <class Impl>
683InstSeqNum
684ROB<Impl>::readTailSeqNum(unsigned tid)
685{
686    // Return the last sequence number that has not been squashed.  Other
687    // stages can use it to squash any instructions younger than the current
688    // tail.
689    //    assert(tail_thread[tid] != instList[tid].end());
690
691    InstIt tail_thread = instList[tid].end();
692    tail_thread--;
693
694    return (*tail_thread)->seqNum;
695}
696*/
697