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