rob_impl.hh revision 13831 
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    : robPolicy(params->smtROBPolicy),
60      cpu(_cpu),
61      numEntries(params->numROBEntries),
62      squashWidth(params->squashWidth),
63      numInstsInROB(0),
64      numThreads(params->numThreads)
65{
66    //Figure out rob policy
67    if (robPolicy == SMTQueuePolicy::Dynamic) {
68        //Set Max Entries to Total ROB Capacity
69        for (ThreadID tid = 0; tid < numThreads; tid++) {
70            maxEntries[tid] = numEntries;
71        }
72
73    } else if (robPolicy == SMTQueuePolicy::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 (robPolicy == SMTQueuePolicy::Threshold) {
85        DPRINTF(Fetch, "ROB sharing policy set to Threshold\n");
86
87        int threshold =  params->smtROBThreshold;;
88
89        //Divide up by threshold amount
90        for (ThreadID tid = 0; tid < numThreads; tid++) {
91            maxEntries[tid] = threshold;
92        }
93    }
94
95    for (ThreadID tid = numThreads; tid < Impl::MaxThreads; tid++) {
96        maxEntries[tid] = 0;
97    }
98
99    resetState();
100}
101
102template <class Impl>
103void
104ROB<Impl>::resetState()
105{
106    for (ThreadID tid = 0; tid  < Impl::MaxThreads; tid++) {
107        threadEntries[tid] = 0;
108        squashIt[tid] = instList[tid].end();
109        squashedSeqNum[tid] = 0;
110        doneSquashing[tid] = true;
111    }
112    numInstsInROB = 0;
113
114    // Initialize the "universal" ROB head & tail point to invalid
115    // pointers
116    head = instList[0].end();
117    tail = instList[0].end();
118}
119
120template <class Impl>
121std::string
122ROB<Impl>::name() const
123{
124    return cpu->name() + ".rob";
125}
126
127template <class Impl>
128void
129ROB<Impl>::setActiveThreads(list<ThreadID> *at_ptr)
130{
131    DPRINTF(ROB, "Setting active threads list pointer.\n");
132    activeThreads = at_ptr;
133}
134
135template <class Impl>
136void
137ROB<Impl>::drainSanityCheck() const
138{
139    for (ThreadID tid = 0; tid  < numThreads; tid++)
140        assert(instList[tid].empty());
141    assert(isEmpty());
142}
143
144template <class Impl>
145void
146ROB<Impl>::takeOverFrom()
147{
148    resetState();
149}
150
151template <class Impl>
152void
153ROB<Impl>::resetEntries()
154{
155    if (robPolicy != SMTQueuePolicy::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 == SMTQueuePolicy::Partitioned) {
165                maxEntries[tid] = numEntries / active_threads;
166            } else if (robPolicy == SMTQueuePolicy::Threshold &&
167                       active_threads == 1) {
168                maxEntries[tid] = numEntries;
169            }
170        }
171    }
172}
173
174template <class Impl>
175int
176ROB<Impl>::entryAmount(ThreadID num_threads)
177{
178    if (robPolicy == SMTQueuePolicy::Partitioned) {
179        return numEntries / num_threads;
180    } else {
181        return 0;
182    }
183}
184
185template <class Impl>
186int
187ROB<Impl>::countInsts()
188{
189    int total = 0;
190
191    for (ThreadID tid = 0; tid < numThreads; tid++)
192        total += countInsts(tid);
193
194    return total;
195}
196
197template <class Impl>
198int
199ROB<Impl>::countInsts(ThreadID tid)
200{
201    return instList[tid].size();
202}
203
204template <class Impl>
205void
206ROB<Impl>::insertInst(const DynInstPtr &inst)
207{
208    assert(inst);
209
210    robWrites++;
211
212    DPRINTF(ROB, "Adding inst PC %s to the ROB.\n", inst->pcState());
213
214    assert(numInstsInROB != numEntries);
215
216    ThreadID tid = inst->threadNumber;
217
218    instList[tid].push_back(inst);
219
220    //Set Up head iterator if this is the 1st instruction in the ROB
221    if (numInstsInROB == 0) {
222        head = instList[tid].begin();
223        assert((*head) == inst);
224    }
225
226    //Must Decrement for iterator to actually be valid  since __.end()
227    //actually points to 1 after the last inst
228    tail = instList[tid].end();
229    tail--;
230
231    inst->setInROB();
232
233    ++numInstsInROB;
234    ++threadEntries[tid];
235
236    assert((*tail) == inst);
237
238    DPRINTF(ROB, "[tid:%i] Now has %d instructions.\n", tid, threadEntries[tid]);
239}
240
241template <class Impl>
242void
243ROB<Impl>::retireHead(ThreadID tid)
244{
245    robWrites++;
246
247    assert(numInstsInROB > 0);
248
249    // Get the head ROB instruction by copying it and remove it from the list
250    InstIt head_it = instList[tid].begin();
251
252    DynInstPtr head_inst = std::move(*head_it);
253    instList[tid].erase(head_it);
254
255    assert(head_inst->readyToCommit());
256
257    DPRINTF(ROB, "[tid:%i] Retiring head instruction, "
258            "instruction PC %s, [sn:%llu]\n", tid, head_inst->pcState(),
259            head_inst->seqNum);
260
261    --numInstsInROB;
262    --threadEntries[tid];
263
264    head_inst->clearInROB();
265    head_inst->setCommitted();
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:%i] Squashing instructions until [sn:%llu].\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:%i] 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:%i] 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:%i] 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    InstSeqNum lowest_num = 0;
403    bool first_valid = true;
404
405    // @todo: set ActiveThreads through ROB or CPU
406    list<ThreadID>::iterator threads = activeThreads->begin();
407    list<ThreadID>::iterator end = activeThreads->end();
408
409    while (threads != end) {
410        ThreadID tid = *threads++;
411
412        if (instList[tid].empty())
413            continue;
414
415        if (first_valid) {
416            head = instList[tid].begin();
417            lowest_num = (*head)->seqNum;
418            first_valid = false;
419            continue;
420        }
421
422        InstIt head_thread = instList[tid].begin();
423
424        DynInstPtr head_inst = (*head_thread);
425
426        assert(head_inst != 0);
427
428        if (head_inst->seqNum < lowest_num) {
429            head = head_thread;
430            lowest_num = head_inst->seqNum;
431        }
432    }
433
434    if (first_valid) {
435        head = instList[0].end();
436    }
437
438}
439
440template <class Impl>
441void
442ROB<Impl>::updateTail()
443{
444    tail = instList[0].end();
445    bool first_valid = true;
446
447    list<ThreadID>::iterator threads = activeThreads->begin();
448    list<ThreadID>::iterator end = activeThreads->end();
449
450    while (threads != end) {
451        ThreadID tid = *threads++;
452
453        if (instList[tid].empty()) {
454            continue;
455        }
456
457        // If this is the first valid then assign w/out
458        // comparison
459        if (first_valid) {
460            tail = instList[tid].end();
461            tail--;
462            first_valid = false;
463            continue;
464        }
465
466        // Assign new tail if this thread's tail is younger
467        // than our current "tail high"
468        InstIt tail_thread = instList[tid].end();
469        tail_thread--;
470
471        if ((*tail_thread)->seqNum > (*tail)->seqNum) {
472            tail = tail_thread;
473        }
474    }
475}
476
477
478template <class Impl>
479void
480ROB<Impl>::squash(InstSeqNum squash_num, ThreadID tid)
481{
482    if (isEmpty(tid)) {
483        DPRINTF(ROB, "Does not need to squash due to being empty "
484                "[sn:%llu]\n",
485                squash_num);
486
487        return;
488    }
489
490    DPRINTF(ROB, "Starting to squash within the ROB.\n");
491
492    robStatus[tid] = ROBSquashing;
493
494    doneSquashing[tid] = false;
495
496    squashedSeqNum[tid] = squash_num;
497
498    if (!instList[tid].empty()) {
499        InstIt tail_thread = instList[tid].end();
500        tail_thread--;
501
502        squashIt[tid] = tail_thread;
503
504        doSquash(tid);
505    }
506}
507
508template <class Impl>
509const typename Impl::DynInstPtr&
510ROB<Impl>::readHeadInst(ThreadID tid)
511{
512    if (threadEntries[tid] != 0) {
513        InstIt head_thread = instList[tid].begin();
514
515        assert((*head_thread)->isInROB());
516
517        return *head_thread;
518    } else {
519        return dummyInst;
520    }
521}
522
523template <class Impl>
524typename Impl::DynInstPtr
525ROB<Impl>::readTailInst(ThreadID tid)
526{
527    InstIt tail_thread = instList[tid].end();
528    tail_thread--;
529
530    return *tail_thread;
531}
532
533template <class Impl>
534void
535ROB<Impl>::regStats()
536{
537    using namespace Stats;
538    robReads
539        .name(name() + ".rob_reads")
540        .desc("The number of ROB reads");
541
542    robWrites
543        .name(name() + ".rob_writes")
544        .desc("The number of ROB writes");
545}
546
547template <class Impl>
548typename Impl::DynInstPtr
549ROB<Impl>::findInst(ThreadID tid, InstSeqNum squash_inst)
550{
551    for (InstIt it = instList[tid].begin(); it != instList[tid].end(); it++) {
552        if ((*it)->seqNum == squash_inst) {
553            return *it;
554        }
555    }
556    return NULL;
557}
558
559#endif//__CPU_O3_ROB_IMPL_HH__
560