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