rob_impl.hh revision 13453 
1/*
2 * Copyright (c) 2012 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder.  You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Copyright (c) 2004-2006 The Regents of The University of Michigan
15 * All rights reserved.
16 *
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions are
19 * met: redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer;
21 * redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution;
24 * neither the name of the copyright holders nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 *
40 * Authors: Kevin Lim
41 *          Korey Sewell
42 */
43
44#ifndef __CPU_O3_ROB_IMPL_HH__
45#define __CPU_O3_ROB_IMPL_HH__
46
47#include <list>
48
49#include "base/logging.hh"
50#include "cpu/o3/rob.hh"
51#include "debug/Fetch.hh"
52#include "debug/ROB.hh"
53#include "params/DerivO3CPU.hh"
54
55using namespace std;
56
57template <class Impl>
58ROB<Impl>::ROB(O3CPU *_cpu, DerivO3CPUParams *params)
59    : cpu(_cpu),
60      numEntries(params->numROBEntries),
61      squashWidth(params->squashWidth),
62      numInstsInROB(0),
63      numThreads(params->numThreads)
64{
65    std::string policy = params->smtROBPolicy;
66
67    //Convert string to lowercase
68    std::transform(policy.begin(), policy.end(), policy.begin(),
69                   (int(*)(int)) tolower);
70
71    //Figure out rob policy
72    if (policy == "dynamic") {
73        robPolicy = Dynamic;
74
75        //Set Max Entries to Total ROB Capacity
76        for (ThreadID tid = 0; tid < numThreads; tid++) {
77            maxEntries[tid] = numEntries;
78        }
79
80    } else if (policy == "partitioned") {
81        robPolicy = Partitioned;
82        DPRINTF(Fetch, "ROB sharing policy set to Partitioned\n");
83
84        //@todo:make work if part_amt doesnt divide evenly.
85        int part_amt = numEntries / numThreads;
86
87        //Divide ROB up evenly
88        for (ThreadID tid = 0; tid < numThreads; tid++) {
89            maxEntries[tid] = part_amt;
90        }
91
92    } else if (policy == "threshold") {
93        robPolicy = Threshold;
94        DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");
95
96        int threshold =  params->smtROBThreshold;;
97
98        //Divide up by threshold amount
99        for (ThreadID tid = 0; tid < numThreads; tid++) {
100            maxEntries[tid] = threshold;
101        }
102    } else {
103        panic("Invalid ROB sharing policy. Options are: Dynamic, "
104                "Partitioned, Threshold");
105    }
106    for (ThreadID tid = numThreads; tid < Impl::MaxThreads; tid++) {
107        maxEntries[tid] = 0;
108    }
109
110    resetState();
111}
112
113template <class Impl>
114void
115ROB<Impl>::resetState()
116{
117    for (ThreadID tid = 0; tid  < Impl::MaxThreads; tid++) {
118        threadEntries[tid] = 0;
119        squashIt[tid] = instList[tid].end();
120        squashedSeqNum[tid] = 0;
121        doneSquashing[tid] = true;
122    }
123    numInstsInROB = 0;
124
125    // Initialize the "universal" ROB head & tail point to invalid
126    // pointers
127    head = instList[0].end();
128    tail = instList[0].end();
129}
130
131template <class Impl>
132std::string
133ROB<Impl>::name() const
134{
135    return cpu->name() + ".rob";
136}
137
138template <class Impl>
139void
140ROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr)
141{
142    DPRINTF(ROB, "Setting active threads list pointer.\n");
143    activeThreads = at_ptr;
144}
145
146template <class Impl>
147void
148ROB<Impl>::drainSanityCheck() const
149{
150    for (ThreadID tid = 0; tid  < numThreads; tid++)
151        assert(instList[tid].empty());
152    assert(isEmpty());
153}
154
155template <class Impl>
156void
157ROB<Impl>::takeOverFrom()
158{
159    resetState();
160}
161
162template <class Impl>
163void
164ROB<Impl>::resetEntries()
165{
166    if (robPolicy != Dynamic || numThreads > 1) {
167        int active_threads = activeThreads->size();
168
169        list<ThreadID>::iterator threads = activeThreads->begin();
170        list<ThreadID>::iterator end = activeThreads->end();
171
172        while (threads != end) {
173            ThreadID tid = *threads++;
174
175            if (robPolicy == Partitioned) {
176                maxEntries[tid] = numEntries / active_threads;
177            } else if (robPolicy == Threshold && active_threads == 1) {
178                maxEntries[tid] = numEntries;
179            }
180        }
181    }
182}
183
184template <class Impl>
185int
186ROB<Impl>::entryAmount(ThreadID num_threads)
187{
188    if (robPolicy == Partitioned) {
189        return numEntries / num_threads;
190    } else {
191        return 0;
192    }
193}
194
195template <class Impl>
196int
197ROB<Impl>::countInsts()
198{
199    int total = 0;
200
201    for (ThreadID tid = 0; tid < numThreads; tid++)
202        total += countInsts(tid);
203
204    return total;
205}
206
207template <class Impl>
208int
209ROB<Impl>::countInsts(ThreadID tid)
210{
211    return instList[tid].size();
212}
213
214template <class Impl>
215void
216ROB<Impl>::insertInst(const DynInstPtr &inst)
217{
218    assert(inst);
219
220    robWrites++;
221
222    DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState());
223
224    assert(numInstsInROB != numEntries);
225
226    ThreadID tid = inst->threadNumber;
227
228    instList[tid].push_back(inst);
229
230    //Set Up head iterator if this is the 1st instruction in the ROB
231    if (numInstsInROB == 0) {
232        head = instList[tid].begin();
233        assert((*head) == inst);
234    }
235
236    //Must Decrement for iterator to actually be valid  since __.end()
237    //actually points to 1 after the last inst
238    tail = instList[tid].end();
239    tail--;
240
241    inst->setInROB();
242
243    ++numInstsInROB;
244    ++threadEntries[tid];
245
246    assert((*tail) == inst);
247
248    DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
249}
250
251template <class Impl>
252void
253ROB<Impl>::retireHead(ThreadID tid)
254{
255    robWrites++;
256
257    assert(numInstsInROB > 0);
258
259    // Get the head ROB instruction by copying it and remove it from the list
260    InstIt head_it = instList[tid].begin();
261
262    DynInstPtr head_inst = std::move(*head_it);
263    instList[tid].erase(head_it);
264
265    assert(head_inst->readyToCommit());
266
267    DPRINTF(ROB, "[tid:%u]: Retiring head instruction, "
268            "instruction PC %s, [sn:%lli]\n", tid, head_inst->pcState(),
269            head_inst->seqNum);
270
271    --numInstsInROB;
272    --threadEntries[tid];
273
274    head_inst->clearInROB();
275    head_inst->setCommitted();
276
277    //Update "Global" Head of ROB
278    updateHead();
279
280    // @todo: A special case is needed if the instruction being
281    // retired is the only instruction in the ROB; otherwise the tail
282    // iterator will become invalidated.
283    cpu->removeFrontInst(head_inst);
284}
285
286template <class Impl>
287bool
288ROB<Impl>::isHeadReady(ThreadID tid)
289{
290    robReads++;
291    if (threadEntries[tid] != 0) {
292        return instList[tid].front()->readyToCommit();
293    }
294
295    return false;
296}
297
298template <class Impl>
299bool
300ROB<Impl>::canCommit()
301{
302    //@todo: set ActiveThreads through ROB or CPU
303    list<ThreadID>::iterator threads = activeThreads->begin();
304    list<ThreadID>::iterator end = activeThreads->end();
305
306    while (threads != end) {
307        ThreadID tid = *threads++;
308
309        if (isHeadReady(tid)) {
310            return true;
311        }
312    }
313
314    return false;
315}
316
317template <class Impl>
318unsigned
319ROB<Impl>::numFreeEntries()
320{
321    return numEntries - numInstsInROB;
322}
323
324template <class Impl>
325unsigned
326ROB<Impl>::numFreeEntries(ThreadID tid)
327{
328    return maxEntries[tid] - threadEntries[tid];
329}
330
331template <class Impl>
332void
333ROB<Impl>::doSquash(ThreadID tid)
334{
335    robWrites++;
336    DPRINTF(ROB, "[tid:%u]: Squashing instructions until [sn:%i].\n",
337            tid, squashedSeqNum[tid]);
338
339    assert(squashIt[tid] != instList[tid].end());
340
341    if ((*squashIt[tid])->seqNum < squashedSeqNum[tid]) {
342        DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
343                tid);
344
345        squashIt[tid] = instList[tid].end();
346
347        doneSquashing[tid] = true;
348        return;
349    }
350
351    bool robTailUpdate = false;
352
353    for (int numSquashed = 0;
354         numSquashed < squashWidth &&
355         squashIt[tid] != instList[tid].end() &&
356         (*squashIt[tid])->seqNum > squashedSeqNum[tid];
357         ++numSquashed)
358    {
359        DPRINTF(ROB, "[tid:%u]: Squashing instruction PC %s, seq num %i.\n",
360                (*squashIt[tid])->threadNumber,
361                (*squashIt[tid])->pcState(),
362                (*squashIt[tid])->seqNum);
363
364        // Mark the instruction as squashed, and ready to commit so that
365        // it can drain out of the pipeline.
366        (*squashIt[tid])->setSquashed();
367
368        (*squashIt[tid])->setCanCommit();
369
370
371        if (squashIt[tid] == instList[tid].begin()) {
372            DPRINTF(ROB, "Reached head of instruction list while "
373                    "squashing.\n");
374
375            squashIt[tid] = instList[tid].end();
376
377            doneSquashing[tid] = true;
378
379            return;
380        }
381
382        InstIt tail_thread = instList[tid].end();
383        tail_thread--;
384
385        if ((*squashIt[tid]) == (*tail_thread))
386            robTailUpdate = true;
387
388        squashIt[tid]--;
389    }
390
391
392    // Check if ROB is done squashing.
393    if ((*squashIt[tid])->seqNum <= squashedSeqNum[tid]) {
394        DPRINTF(ROB, "[tid:%u]: Done squashing instructions.\n",
395                tid);
396
397        squashIt[tid] = instList[tid].end();
398
399        doneSquashing[tid] = true;
400    }
401
402    if (robTailUpdate) {
403        updateTail();
404    }
405}
406
407
408template <class Impl>
409void
410ROB<Impl>::updateHead()
411{
412    InstSeqNum lowest_num = 0;
413    bool first_valid = true;
414
415    // @todo: set ActiveThreads through ROB or CPU
416    list<ThreadID>::iterator threads = activeThreads->begin();
417    list<ThreadID>::iterator end = activeThreads->end();
418
419    while (threads != end) {
420        ThreadID tid = *threads++;
421
422        if (instList[tid].empty())
423            continue;
424
425        if (first_valid) {
426            head = instList[tid].begin();
427            lowest_num = (*head)->seqNum;
428            first_valid = false;
429            continue;
430        }
431
432        InstIt head_thread = instList[tid].begin();
433
434        DynInstPtr head_inst = (*head_thread);
435
436        assert(head_inst != 0);
437
438        if (head_inst->seqNum < lowest_num) {
439            head = head_thread;
440            lowest_num = head_inst->seqNum;
441        }
442    }
443
444    if (first_valid) {
445        head = instList[0].end();
446    }
447
448}
449
450template <class Impl>
451void
452ROB<Impl>::updateTail()
453{
454    tail = instList[0].end();
455    bool first_valid = true;
456
457    list<ThreadID>::iterator threads = activeThreads->begin();
458    list<ThreadID>::iterator end = activeThreads->end();
459
460    while (threads != end) {
461        ThreadID tid = *threads++;
462
463        if (instList[tid].empty()) {
464            continue;
465        }
466
467        // If this is the first valid then assign w/out
468        // comparison
469        if (first_valid) {
470            tail = instList[tid].end();
471            tail--;
472            first_valid = false;
473            continue;
474        }
475
476        // Assign new tail if this thread's tail is younger
477        // than our current "tail high"
478        InstIt tail_thread = instList[tid].end();
479        tail_thread--;
480
481        if ((*tail_thread)->seqNum > (*tail)->seqNum) {
482            tail = tail_thread;
483        }
484    }
485}
486
487
488template <class Impl>
489void
490ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid)
491{
492    if (isEmpty(tid)) {
493        DPRINTF(ROB, "Does not need to squash due to being empty "
494                "[sn:%i]\n",
495                squash_num);
496
497        return;
498    }
499
500    DPRINTF(ROB, "Starting to squash within the ROB.\n");
501
502    robStatus[tid] = ROBSquashing;
503
504    doneSquashing[tid] = false;
505
506    squashedSeqNum[tid] = squash_num;
507
508    if (!instList[tid].empty()) {
509        InstIt tail_thread = instList[tid].end();
510        tail_thread--;
511
512        squashIt[tid] = tail_thread;
513
514        doSquash(tid);
515    }
516}
517
518template <class Impl>
519const typename Impl::DynInstPtr&
520ROB<Impl>::readHeadInst(ThreadID tid)
521{
522    if (threadEntries[tid] != 0) {
523        InstIt head_thread = instList[tid].begin();
524
525        assert((*head_thread)->isInROB());
526
527        return *head_thread;
528    } else {
529        return dummyInst;
530    }
531}
532
533template <class Impl>
534typename Impl::DynInstPtr
535ROB<Impl>::readTailInst(ThreadID tid)
536{
537    InstIt tail_thread = instList[tid].end();
538    tail_thread--;
539
540    return *tail_thread;
541}
542
543template <class Impl>
544void
545ROB<Impl>::regStats()
546{
547    using namespace Stats;
548    robReads
549        .name(name() + ".rob_reads")
550        .desc("The number of ROB reads");
551
552    robWrites
553        .name(name() + ".rob_writes")
554        .desc("The number of ROB writes");
555}
556
557template <class Impl>
558typename Impl::DynInstPtr
559ROB<Impl>::findInst(ThreadID tid, InstSeqNum squash_inst)
560{
561    for (InstIt it = instList[tid].begin(); it != instList[tid].end(); it++) {
562        if ((*it)->seqNum == squash_inst) {
563            return *it;
564        }
565    }
566    return NULL;
567}
568
569#endif//__CPU_O3_ROB_IMPL_HH__
570