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