inst_queue_impl.hh revision 2665:a124942bacb8
1/*
2 * Copyright (c) 2004-2005 The Regents of The University of Michigan
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Kevin Lim
29 */
30
31// Todo:
32// Current ordering allows for 0 cycle added-to-scheduled.  Could maybe fake
33// it; either do in reverse order, or have added instructions put into a
34// different ready queue that, in scheduleRreadyInsts(), gets put onto the
35// normal ready queue.  This would however give only a one cycle delay,
36// but probably is more flexible to actually add in a delay parameter than
37// just running it backwards.
38
39#include <limits>
40#include <vector>
41
42#include "sim/root.hh"
43
44#include "cpu/o3/inst_queue.hh"
45
46// Either compile error or max int due to sign extension.
47// Hack to avoid compile warnings.
48const InstSeqNum MaxInstSeqNum = std::numeric_limits<InstSeqNum>::max();
49
50template <class Impl>
51InstructionQueue<Impl>::InstructionQueue(Params &params)
52    : memDepUnit(params),
53      numEntries(params.numIQEntries),
54      intWidth(params.executeIntWidth),
55      floatWidth(params.executeFloatWidth),
56      branchWidth(params.executeBranchWidth),
57      memoryWidth(params.executeMemoryWidth),
58      totalWidth(params.issueWidth),
59      numPhysIntRegs(params.numPhysIntRegs),
60      numPhysFloatRegs(params.numPhysFloatRegs),
61      commitToIEWDelay(params.commitToIEWDelay)
62{
63    // Initialize the number of free IQ entries.
64    freeEntries = numEntries;
65
66    // Set the number of physical registers as the number of int + float
67    numPhysRegs = numPhysIntRegs + numPhysFloatRegs;
68
69    DPRINTF(IQ, "IQ: There are %i physical registers.\n", numPhysRegs);
70
71    //Create an entry for each physical register within the
72    //dependency graph.
73    dependGraph = new DependencyEntry[numPhysRegs];
74
75    // Resize the register scoreboard.
76    regScoreboard.resize(numPhysRegs);
77
78    // Initialize all the head pointers to point to NULL, and all the
79    // entries as unready.
80    // Note that in actuality, the registers corresponding to the logical
81    // registers start off as ready.  However this doesn't matter for the
82    // IQ as the instruction should have been correctly told if those
83    // registers are ready in rename.  Thus it can all be initialized as
84    // unready.
85    for (int i = 0; i < numPhysRegs; ++i)
86    {
87        dependGraph[i].next = NULL;
88        dependGraph[i].inst = NULL;
89        regScoreboard[i] = false;
90    }
91
92}
93
94template <class Impl>
95void
96InstructionQueue<Impl>::regStats()
97{
98    iqInstsAdded
99        .name(name() + ".iqInstsAdded")
100        .desc("Number of instructions added to the IQ (excludes non-spec)")
101        .prereq(iqInstsAdded);
102
103    iqNonSpecInstsAdded
104        .name(name() + ".iqNonSpecInstsAdded")
105        .desc("Number of non-speculative instructions added to the IQ")
106        .prereq(iqNonSpecInstsAdded);
107
108//    iqIntInstsAdded;
109
110    iqIntInstsIssued
111        .name(name() + ".iqIntInstsIssued")
112        .desc("Number of integer instructions issued")
113        .prereq(iqIntInstsIssued);
114
115//    iqFloatInstsAdded;
116
117    iqFloatInstsIssued
118        .name(name() + ".iqFloatInstsIssued")
119        .desc("Number of float instructions issued")
120        .prereq(iqFloatInstsIssued);
121
122//    iqBranchInstsAdded;
123
124    iqBranchInstsIssued
125        .name(name() + ".iqBranchInstsIssued")
126        .desc("Number of branch instructions issued")
127        .prereq(iqBranchInstsIssued);
128
129//    iqMemInstsAdded;
130
131    iqMemInstsIssued
132        .name(name() + ".iqMemInstsIssued")
133        .desc("Number of memory instructions issued")
134        .prereq(iqMemInstsIssued);
135
136//    iqMiscInstsAdded;
137
138    iqMiscInstsIssued
139        .name(name() + ".iqMiscInstsIssued")
140        .desc("Number of miscellaneous instructions issued")
141        .prereq(iqMiscInstsIssued);
142
143    iqSquashedInstsIssued
144        .name(name() + ".iqSquashedInstsIssued")
145        .desc("Number of squashed instructions issued")
146        .prereq(iqSquashedInstsIssued);
147
148    iqLoopSquashStalls
149        .name(name() + ".iqLoopSquashStalls")
150        .desc("Number of times issue loop had to restart due to squashed "
151              "inst; mainly for profiling")
152        .prereq(iqLoopSquashStalls);
153
154    iqSquashedInstsExamined
155        .name(name() + ".iqSquashedInstsExamined")
156        .desc("Number of squashed instructions iterated over during squash;"
157              " mainly for profiling")
158        .prereq(iqSquashedInstsExamined);
159
160    iqSquashedOperandsExamined
161        .name(name() + ".iqSquashedOperandsExamined")
162        .desc("Number of squashed operands that are examined and possibly "
163              "removed from graph")
164        .prereq(iqSquashedOperandsExamined);
165
166    iqSquashedNonSpecRemoved
167        .name(name() + ".iqSquashedNonSpecRemoved")
168        .desc("Number of squashed non-spec instructions that were removed")
169        .prereq(iqSquashedNonSpecRemoved);
170
171    // Tell mem dependence unit to reg stats as well.
172    memDepUnit.regStats();
173}
174
175template <class Impl>
176void
177InstructionQueue<Impl>::setCPU(FullCPU *cpu_ptr)
178{
179    cpu = cpu_ptr;
180
181    tail = cpu->instList.begin();
182}
183
184template <class Impl>
185void
186InstructionQueue<Impl>::setIssueToExecuteQueue(
187                        TimeBuffer<IssueStruct> *i2e_ptr)
188{
189    DPRINTF(IQ, "IQ: Set the issue to execute queue.\n");
190    issueToExecuteQueue = i2e_ptr;
191}
192
193template <class Impl>
194void
195InstructionQueue<Impl>::setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr)
196{
197    DPRINTF(IQ, "IQ: Set the time buffer.\n");
198    timeBuffer = tb_ptr;
199
200    fromCommit = timeBuffer->getWire(-commitToIEWDelay);
201}
202
203template <class Impl>
204unsigned
205InstructionQueue<Impl>::numFreeEntries()
206{
207    return freeEntries;
208}
209
210// Might want to do something more complex if it knows how many instructions
211// will be issued this cycle.
212template <class Impl>
213bool
214InstructionQueue<Impl>::isFull()
215{
216    if (freeEntries == 0) {
217        return(true);
218    } else {
219        return(false);
220    }
221}
222
223template <class Impl>
224void
225InstructionQueue<Impl>::insert(DynInstPtr &new_inst)
226{
227    // Make sure the instruction is valid
228    assert(new_inst);
229
230    DPRINTF(IQ, "IQ: Adding instruction PC %#x to the IQ.\n",
231            new_inst->readPC());
232
233    // Check if there are any free entries.  Panic if there are none.
234    // Might want to have this return a fault in the future instead of
235    // panicing.
236    assert(freeEntries != 0);
237
238    // If the IQ currently has nothing in it, then there's a possibility
239    // that the tail iterator is invalid (might have been pointing at an
240    // instruction that was retired).  Reset the tail iterator.
241    if (freeEntries == numEntries) {
242        tail = cpu->instList.begin();
243    }
244
245    // Move the tail iterator.  Instructions may not have been issued
246    // to the IQ, so we may have to increment the iterator more than once.
247    while ((*tail) != new_inst) {
248        tail++;
249
250        // Make sure the tail iterator points at something legal.
251        assert(tail != cpu->instList.end());
252    }
253
254
255    // Decrease the number of free entries.
256    --freeEntries;
257
258    // Look through its source registers (physical regs), and mark any
259    // dependencies.
260    addToDependents(new_inst);
261
262    // Have this instruction set itself as the producer of its destination
263    // register(s).
264    createDependency(new_inst);
265
266    // If it's a memory instruction, add it to the memory dependency
267    // unit.
268    if (new_inst->isMemRef()) {
269        memDepUnit.insert(new_inst);
270        // Uh..forgot to look it up and put it on the proper dependency list
271        // if the instruction should not go yet.
272    } else {
273        // If the instruction is ready then add it to the ready list.
274        addIfReady(new_inst);
275    }
276
277    ++iqInstsAdded;
278
279    assert(freeEntries == (numEntries - countInsts()));
280}
281
282template <class Impl>
283void
284InstructionQueue<Impl>::insertNonSpec(DynInstPtr &inst)
285{
286    nonSpecInsts[inst->seqNum] = inst;
287
288    // @todo: Clean up this code; can do it by setting inst as unable
289    // to issue, then calling normal insert on the inst.
290
291    // Make sure the instruction is valid
292    assert(inst);
293
294    DPRINTF(IQ, "IQ: Adding instruction PC %#x to the IQ.\n",
295            inst->readPC());
296
297    // Check if there are any free entries.  Panic if there are none.
298    // Might want to have this return a fault in the future instead of
299    // panicing.
300    assert(freeEntries != 0);
301
302    // If the IQ currently has nothing in it, then there's a possibility
303    // that the tail iterator is invalid (might have been pointing at an
304    // instruction that was retired).  Reset the tail iterator.
305    if (freeEntries == numEntries) {
306        tail = cpu->instList.begin();
307    }
308
309    // Move the tail iterator.  Instructions may not have been issued
310    // to the IQ, so we may have to increment the iterator more than once.
311    while ((*tail) != inst) {
312        tail++;
313
314        // Make sure the tail iterator points at something legal.
315        assert(tail != cpu->instList.end());
316    }
317
318    // Decrease the number of free entries.
319    --freeEntries;
320
321    // Have this instruction set itself as the producer of its destination
322    // register(s).
323    createDependency(inst);
324
325    // If it's a memory instruction, add it to the memory dependency
326    // unit.
327    if (inst->isMemRef()) {
328        memDepUnit.insertNonSpec(inst);
329    }
330
331    ++iqNonSpecInstsAdded;
332}
333
334// Slightly hack function to advance the tail iterator in the case that
335// the IEW stage issues an instruction that is not added to the IQ.  This
336// is needed in case a long chain of such instructions occurs.
337// I don't think this is used anymore.
338template <class Impl>
339void
340InstructionQueue<Impl>::advanceTail(DynInstPtr &inst)
341{
342    // Make sure the instruction is valid
343    assert(inst);
344
345    DPRINTF(IQ, "IQ: Adding instruction PC %#x to the IQ.\n",
346            inst->readPC());
347
348    // Check if there are any free entries.  Panic if there are none.
349    // Might want to have this return a fault in the future instead of
350    // panicing.
351    assert(freeEntries != 0);
352
353    // If the IQ currently has nothing in it, then there's a possibility
354    // that the tail iterator is invalid (might have been pointing at an
355    // instruction that was retired).  Reset the tail iterator.
356    if (freeEntries == numEntries) {
357        tail = cpu->instList.begin();
358    }
359
360    // Move the tail iterator.  Instructions may not have been issued
361    // to the IQ, so we may have to increment the iterator more than once.
362    while ((*tail) != inst) {
363        tail++;
364
365        // Make sure the tail iterator points at something legal.
366        assert(tail != cpu->instList.end());
367    }
368
369    assert(freeEntries <= numEntries);
370
371    // Have this instruction set itself as the producer of its destination
372    // register(s).
373    createDependency(inst);
374}
375
376// Need to make sure the number of float and integer instructions
377// issued does not exceed the total issue bandwidth.
378// @todo: Figure out a better way to remove the squashed items from the
379// lists.  Checking the top item of each list to see if it's squashed
380// wastes time and forces jumps.
381template <class Impl>
382void
383InstructionQueue<Impl>::scheduleReadyInsts()
384{
385    DPRINTF(IQ, "IQ: Attempting to schedule ready instructions from "
386                "the IQ.\n");
387
388    int int_issued = 0;
389    int float_issued = 0;
390    int branch_issued = 0;
391    int memory_issued = 0;
392    int squashed_issued = 0;
393    int total_issued = 0;
394
395    IssueStruct *i2e_info = issueToExecuteQueue->access(0);
396
397    bool insts_available = !readyBranchInsts.empty() ||
398        !readyIntInsts.empty() ||
399        !readyFloatInsts.empty() ||
400        !memDepUnit.empty() ||
401        !readyMiscInsts.empty() ||
402        !squashedInsts.empty();
403
404    // Note: Requires a globally defined constant.
405    InstSeqNum oldest_inst = MaxInstSeqNum;
406    InstList list_with_oldest = None;
407
408    // Temporary values.
409    DynInstPtr int_head_inst;
410    DynInstPtr float_head_inst;
411    DynInstPtr branch_head_inst;
412    DynInstPtr mem_head_inst;
413    DynInstPtr misc_head_inst;
414    DynInstPtr squashed_head_inst;
415
416    // Somewhat nasty code to look at all of the lists where issuable
417    // instructions are located, and choose the oldest instruction among
418    // those lists.  Consider a rewrite in the future.
419    while (insts_available && total_issued < totalWidth)
420    {
421        // Set this to false.  Each if-block is required to set it to true
422        // if there were instructions available this check.  This will cause
423        // this loop to run once more than necessary, but avoids extra calls.
424        insts_available = false;
425
426        oldest_inst = MaxInstSeqNum;
427
428        list_with_oldest = None;
429
430        if (!readyIntInsts.empty() &&
431            int_issued < intWidth) {
432
433            insts_available = true;
434
435            int_head_inst = readyIntInsts.top();
436
437            if (int_head_inst->isSquashed()) {
438                readyIntInsts.pop();
439
440                ++iqLoopSquashStalls;
441
442                continue;
443            }
444
445            oldest_inst = int_head_inst->seqNum;
446
447            list_with_oldest = Int;
448        }
449
450        if (!readyFloatInsts.empty() &&
451            float_issued < floatWidth) {
452
453            insts_available = true;
454
455            float_head_inst = readyFloatInsts.top();
456
457            if (float_head_inst->isSquashed()) {
458                readyFloatInsts.pop();
459
460                ++iqLoopSquashStalls;
461
462                continue;
463            } else if (float_head_inst->seqNum < oldest_inst) {
464                oldest_inst = float_head_inst->seqNum;
465
466                list_with_oldest = Float;
467            }
468        }
469
470        if (!readyBranchInsts.empty() &&
471            branch_issued < branchWidth) {
472
473            insts_available = true;
474
475            branch_head_inst = readyBranchInsts.top();
476
477            if (branch_head_inst->isSquashed()) {
478                readyBranchInsts.pop();
479
480                ++iqLoopSquashStalls;
481
482                continue;
483            } else if (branch_head_inst->seqNum < oldest_inst) {
484                oldest_inst = branch_head_inst->seqNum;
485
486                list_with_oldest = Branch;
487            }
488
489        }
490
491        if (!memDepUnit.empty() &&
492            memory_issued < memoryWidth) {
493
494            insts_available = true;
495
496            mem_head_inst = memDepUnit.top();
497
498            if (mem_head_inst->isSquashed()) {
499                memDepUnit.pop();
500
501                ++iqLoopSquashStalls;
502
503                continue;
504            } else if (mem_head_inst->seqNum < oldest_inst) {
505                oldest_inst = mem_head_inst->seqNum;
506
507                list_with_oldest = Memory;
508            }
509        }
510
511        if (!readyMiscInsts.empty()) {
512
513            insts_available = true;
514
515            misc_head_inst = readyMiscInsts.top();
516
517            if (misc_head_inst->isSquashed()) {
518                readyMiscInsts.pop();
519
520                ++iqLoopSquashStalls;
521
522                continue;
523            } else if (misc_head_inst->seqNum < oldest_inst) {
524                oldest_inst = misc_head_inst->seqNum;
525
526                list_with_oldest = Misc;
527            }
528        }
529
530        if (!squashedInsts.empty()) {
531
532            insts_available = true;
533
534            squashed_head_inst = squashedInsts.top();
535
536            if (squashed_head_inst->seqNum < oldest_inst) {
537                list_with_oldest = Squashed;
538            }
539
540        }
541
542        DynInstPtr issuing_inst = NULL;
543
544        switch (list_with_oldest) {
545          case None:
546            DPRINTF(IQ, "IQ: Not able to schedule any instructions. Issuing "
547                    "inst is %#x.\n", issuing_inst);
548            break;
549
550          case Int:
551            issuing_inst = int_head_inst;
552            readyIntInsts.pop();
553            ++int_issued;
554            DPRINTF(IQ, "IQ: Issuing integer instruction PC %#x.\n",
555                    issuing_inst->readPC());
556            break;
557
558          case Float:
559            issuing_inst = float_head_inst;
560            readyFloatInsts.pop();
561            ++float_issued;
562            DPRINTF(IQ, "IQ: Issuing float instruction PC %#x.\n",
563                    issuing_inst->readPC());
564            break;
565
566          case Branch:
567            issuing_inst = branch_head_inst;
568            readyBranchInsts.pop();
569            ++branch_issued;
570            DPRINTF(IQ, "IQ: Issuing branch instruction PC %#x.\n",
571                    issuing_inst->readPC());
572            break;
573
574          case Memory:
575            issuing_inst = mem_head_inst;
576
577            memDepUnit.pop();
578            ++memory_issued;
579            DPRINTF(IQ, "IQ: Issuing memory instruction PC %#x.\n",
580                    issuing_inst->readPC());
581            break;
582
583          case Misc:
584            issuing_inst = misc_head_inst;
585            readyMiscInsts.pop();
586
587            ++iqMiscInstsIssued;
588
589            DPRINTF(IQ, "IQ: Issuing a miscellaneous instruction PC %#x.\n",
590                    issuing_inst->readPC());
591            break;
592
593          case Squashed:
594            assert(0 && "Squashed insts should not issue any more!");
595            squashedInsts.pop();
596            // Set the squashed instruction as able to commit so that commit
597            // can just drop it from the ROB.  This is a bit faked.
598            ++squashed_issued;
599            ++freeEntries;
600
601            DPRINTF(IQ, "IQ: Issuing squashed instruction PC %#x.\n",
602                    squashed_head_inst->readPC());
603            break;
604        }
605
606        if (list_with_oldest != None && list_with_oldest != Squashed) {
607            i2e_info->insts[total_issued] = issuing_inst;
608            i2e_info->size++;
609
610            issuing_inst->setIssued();
611
612            ++freeEntries;
613            ++total_issued;
614        }
615
616        assert(freeEntries == (numEntries - countInsts()));
617    }
618
619    iqIntInstsIssued += int_issued;
620    iqFloatInstsIssued += float_issued;
621    iqBranchInstsIssued += branch_issued;
622    iqMemInstsIssued += memory_issued;
623    iqSquashedInstsIssued += squashed_issued;
624}
625
626template <class Impl>
627void
628InstructionQueue<Impl>::scheduleNonSpec(const InstSeqNum &inst)
629{
630    DPRINTF(IQ, "IQ: Marking nonspeculative instruction with sequence "
631            "number %i as ready to execute.\n", inst);
632
633    non_spec_it_t inst_it = nonSpecInsts.find(inst);
634
635    assert(inst_it != nonSpecInsts.end());
636
637    // Mark this instruction as ready to issue.
638    (*inst_it).second->setCanIssue();
639
640    // Now schedule the instruction.
641    if (!(*inst_it).second->isMemRef()) {
642        addIfReady((*inst_it).second);
643    } else {
644        memDepUnit.nonSpecInstReady((*inst_it).second);
645    }
646
647    nonSpecInsts.erase(inst_it);
648}
649
650template <class Impl>
651void
652InstructionQueue<Impl>::wakeDependents(DynInstPtr &completed_inst)
653{
654    DPRINTF(IQ, "IQ: Waking dependents of completed instruction.\n");
655    //Look at the physical destination register of the DynInst
656    //and look it up on the dependency graph.  Then mark as ready
657    //any instructions within the instruction queue.
658    DependencyEntry *curr;
659
660    // Tell the memory dependence unit to wake any dependents on this
661    // instruction if it is a memory instruction.
662
663    if (completed_inst->isMemRef()) {
664        memDepUnit.wakeDependents(completed_inst);
665    }
666
667    for (int dest_reg_idx = 0;
668         dest_reg_idx < completed_inst->numDestRegs();
669         dest_reg_idx++)
670    {
671        PhysRegIndex dest_reg =
672            completed_inst->renamedDestRegIdx(dest_reg_idx);
673
674        // Special case of uniq or control registers.  They are not
675        // handled by the IQ and thus have no dependency graph entry.
676        // @todo Figure out a cleaner way to handle this.
677        if (dest_reg >= numPhysRegs) {
678            continue;
679        }
680
681        DPRINTF(IQ, "IQ: Waking any dependents on register %i.\n",
682                (int) dest_reg);
683
684        //Maybe abstract this part into a function.
685        //Go through the dependency chain, marking the registers as ready
686        //within the waiting instructions.
687        while (dependGraph[dest_reg].next) {
688
689            curr = dependGraph[dest_reg].next;
690
691            DPRINTF(IQ, "IQ: Waking up a dependent instruction, PC%#x.\n",
692                    curr->inst->readPC());
693
694            // Might want to give more information to the instruction
695            // so that it knows which of its source registers is ready.
696            // However that would mean that the dependency graph entries
697            // would need to hold the src_reg_idx.
698            curr->inst->markSrcRegReady();
699
700            addIfReady(curr->inst);
701
702            dependGraph[dest_reg].next = curr->next;
703
704            DependencyEntry::mem_alloc_counter--;
705
706            curr->inst = NULL;
707
708            delete curr;
709        }
710
711        // Reset the head node now that all of its dependents have been woken
712        // up.
713        dependGraph[dest_reg].next = NULL;
714        dependGraph[dest_reg].inst = NULL;
715
716        // Mark the scoreboard as having that register ready.
717        regScoreboard[dest_reg] = true;
718    }
719}
720
721template <class Impl>
722void
723InstructionQueue<Impl>::violation(DynInstPtr &store,
724                                  DynInstPtr &faulting_load)
725{
726    memDepUnit.violation(store, faulting_load);
727}
728
729template <class Impl>
730void
731InstructionQueue<Impl>::squash()
732{
733    DPRINTF(IQ, "IQ: Starting to squash instructions in the IQ.\n");
734
735    // Read instruction sequence number of last instruction out of the
736    // time buffer.
737    squashedSeqNum = fromCommit->commitInfo.doneSeqNum;
738
739    // Setup the squash iterator to point to the tail.
740    squashIt = tail;
741
742    // Call doSquash if there are insts in the IQ
743    if (freeEntries != numEntries) {
744        doSquash();
745    }
746
747    // Also tell the memory dependence unit to squash.
748    memDepUnit.squash(squashedSeqNum);
749}
750
751template <class Impl>
752void
753InstructionQueue<Impl>::doSquash()
754{
755    // Make sure the squash iterator isn't pointing to nothing.
756    assert(squashIt != cpu->instList.end());
757    // Make sure the squashed sequence number is valid.
758    assert(squashedSeqNum != 0);
759
760    DPRINTF(IQ, "IQ: Squashing instructions in the IQ.\n");
761
762    // Squash any instructions younger than the squashed sequence number
763    // given.
764    while ((*squashIt)->seqNum > squashedSeqNum) {
765        DynInstPtr squashed_inst = (*squashIt);
766
767        // Only handle the instruction if it actually is in the IQ and
768        // hasn't already been squashed in the IQ.
769        if (!squashed_inst->isIssued() &&
770            !squashed_inst->isSquashedInIQ()) {
771
772            // Remove the instruction from the dependency list.
773            // Hack for now: These below don't add themselves to the
774            // dependency list, so don't try to remove them.
775            if (!squashed_inst->isNonSpeculative()/* &&
776                                                     !squashed_inst->isStore()*/
777                ) {
778
779                for (int src_reg_idx = 0;
780                     src_reg_idx < squashed_inst->numSrcRegs();
781                     src_reg_idx++)
782                {
783                    PhysRegIndex src_reg =
784                        squashed_inst->renamedSrcRegIdx(src_reg_idx);
785
786                    // Only remove it from the dependency graph if it was
787                    // placed there in the first place.
788                    // HACK: This assumes that instructions woken up from the
789                    // dependency chain aren't informed that a specific src
790                    // register has become ready.  This may not always be true
791                    // in the future.
792                    if (!squashed_inst->isReadySrcRegIdx(src_reg_idx) &&
793                        src_reg < numPhysRegs) {
794                        dependGraph[src_reg].remove(squashed_inst);
795                    }
796
797                    ++iqSquashedOperandsExamined;
798                }
799
800                // Might want to remove producers as well.
801            } else {
802                nonSpecInsts[squashed_inst->seqNum] = NULL;
803
804                nonSpecInsts.erase(squashed_inst->seqNum);
805
806                ++iqSquashedNonSpecRemoved;
807            }
808
809            // Might want to also clear out the head of the dependency graph.
810
811            // Mark it as squashed within the IQ.
812            squashed_inst->setSquashedInIQ();
813
814//            squashedInsts.push(squashed_inst);
815            squashed_inst->setIssued();
816            squashed_inst->setCanCommit();
817
818            ++freeEntries;
819
820            DPRINTF(IQ, "IQ: Instruction PC %#x squashed.\n",
821                    squashed_inst->readPC());
822        }
823
824        --squashIt;
825        ++iqSquashedInstsExamined;
826    }
827
828    assert(freeEntries <= numEntries);
829
830    if (freeEntries == numEntries) {
831        tail = cpu->instList.end();
832    }
833
834}
835
836template <class Impl>
837void
838InstructionQueue<Impl>::stopSquash()
839{
840    // Clear up the squash variables to ensure that squashing doesn't
841    // get called improperly.
842    squashedSeqNum = 0;
843
844    squashIt = cpu->instList.end();
845}
846
847template <class Impl>
848void
849InstructionQueue<Impl>::DependencyEntry::insert(DynInstPtr &new_inst)
850{
851    //Add this new, dependent instruction at the head of the dependency
852    //chain.
853
854    // First create the entry that will be added to the head of the
855    // dependency chain.
856    DependencyEntry *new_entry = new DependencyEntry;
857    new_entry->next = this->next;
858    new_entry->inst = new_inst;
859
860    // Then actually add it to the chain.
861    this->next = new_entry;
862
863    ++mem_alloc_counter;
864}
865
866template <class Impl>
867void
868InstructionQueue<Impl>::DependencyEntry::remove(DynInstPtr &inst_to_remove)
869{
870    DependencyEntry *prev = this;
871    DependencyEntry *curr = this->next;
872
873    // Make sure curr isn't NULL.  Because this instruction is being
874    // removed from a dependency list, it must have been placed there at
875    // an earlier time.  The dependency chain should not be empty,
876    // unless the instruction dependent upon it is already ready.
877    if (curr == NULL) {
878        return;
879    }
880
881    // Find the instruction to remove within the dependency linked list.
882    while(curr->inst != inst_to_remove)
883    {
884        prev = curr;
885        curr = curr->next;
886
887        assert(curr != NULL);
888    }
889
890    // Now remove this instruction from the list.
891    prev->next = curr->next;
892
893    --mem_alloc_counter;
894
895    // Could push this off to the destructor of DependencyEntry
896    curr->inst = NULL;
897
898    delete curr;
899}
900
901template <class Impl>
902bool
903InstructionQueue<Impl>::addToDependents(DynInstPtr &new_inst)
904{
905    // Loop through the instruction's source registers, adding
906    // them to the dependency list if they are not ready.
907    int8_t total_src_regs = new_inst->numSrcRegs();
908    bool return_val = false;
909
910    for (int src_reg_idx = 0;
911         src_reg_idx < total_src_regs;
912         src_reg_idx++)
913    {
914        // Only add it to the dependency graph if it's not ready.
915        if (!new_inst->isReadySrcRegIdx(src_reg_idx)) {
916            PhysRegIndex src_reg = new_inst->renamedSrcRegIdx(src_reg_idx);
917
918            // Check the IQ's scoreboard to make sure the register
919            // hasn't become ready while the instruction was in flight
920            // between stages.  Only if it really isn't ready should
921            // it be added to the dependency graph.
922            if (src_reg >= numPhysRegs) {
923                continue;
924            } else if (regScoreboard[src_reg] == false) {
925                DPRINTF(IQ, "IQ: Instruction PC %#x has src reg %i that "
926                        "is being added to the dependency chain.\n",
927                        new_inst->readPC(), src_reg);
928
929                dependGraph[src_reg].insert(new_inst);
930
931                // Change the return value to indicate that something
932                // was added to the dependency graph.
933                return_val = true;
934            } else {
935                DPRINTF(IQ, "IQ: Instruction PC %#x has src reg %i that "
936                        "became ready before it reached the IQ.\n",
937                        new_inst->readPC(), src_reg);
938                // Mark a register ready within the instruction.
939                new_inst->markSrcRegReady();
940            }
941        }
942    }
943
944    return return_val;
945}
946
947template <class Impl>
948void
949InstructionQueue<Impl>::createDependency(DynInstPtr &new_inst)
950{
951    //Actually nothing really needs to be marked when an
952    //instruction becomes the producer of a register's value,
953    //but for convenience a ptr to the producing instruction will
954    //be placed in the head node of the dependency links.
955    int8_t total_dest_regs = new_inst->numDestRegs();
956
957    for (int dest_reg_idx = 0;
958         dest_reg_idx < total_dest_regs;
959         dest_reg_idx++)
960    {
961        PhysRegIndex dest_reg = new_inst->renamedDestRegIdx(dest_reg_idx);
962
963        // Instructions that use the misc regs will have a reg number
964        // higher than the normal physical registers.  In this case these
965        // registers are not renamed, and there is no need to track
966        // dependencies as these instructions must be executed at commit.
967        if (dest_reg >= numPhysRegs) {
968            continue;
969        }
970
971        dependGraph[dest_reg].inst = new_inst;
972
973        if (dependGraph[dest_reg].next) {
974            dumpDependGraph();
975            panic("IQ: Dependency graph not empty!");
976        }
977
978        // Mark the scoreboard to say it's not yet ready.
979        regScoreboard[dest_reg] = false;
980    }
981}
982
983template <class Impl>
984void
985InstructionQueue<Impl>::addIfReady(DynInstPtr &inst)
986{
987    //If the instruction now has all of its source registers
988    // available, then add it to the list of ready instructions.
989    if (inst->readyToIssue()) {
990
991        //Add the instruction to the proper ready list.
992        if (inst->isControl()) {
993
994            DPRINTF(IQ, "IQ: Branch instruction is ready to issue, "
995                    "putting it onto the ready list, PC %#x.\n",
996                    inst->readPC());
997            readyBranchInsts.push(inst);
998
999        } else if (inst->isMemRef()) {
1000
1001            DPRINTF(IQ, "IQ: Checking if memory instruction can issue.\n");
1002
1003            // Message to the mem dependence unit that this instruction has
1004            // its registers ready.
1005
1006            memDepUnit.regsReady(inst);
1007
1008#if 0
1009            if (memDepUnit.readyToIssue(inst)) {
1010                DPRINTF(IQ, "IQ: Memory instruction is ready to issue, "
1011                        "putting it onto the ready list, PC %#x.\n",
1012                        inst->readPC());
1013                readyMemInsts.push(inst);
1014            } else {
1015                // Make dependent on the store.
1016                // Will need some way to get the store instruction it should
1017                // be dependent upon; then when the store issues it can
1018                // put the instruction on the ready list.
1019                // Yet another tree?
1020                assert(0 && "Instruction has no way to actually issue");
1021            }
1022#endif
1023
1024        } else if (inst->isInteger()) {
1025
1026            DPRINTF(IQ, "IQ: Integer instruction is ready to issue, "
1027                    "putting it onto the ready list, PC %#x.\n",
1028                    inst->readPC());
1029            readyIntInsts.push(inst);
1030
1031        } else if (inst->isFloating()) {
1032
1033            DPRINTF(IQ, "IQ: Floating instruction is ready to issue, "
1034                    "putting it onto the ready list, PC %#x.\n",
1035                    inst->readPC());
1036            readyFloatInsts.push(inst);
1037
1038        } else {
1039            DPRINTF(IQ, "IQ: Miscellaneous instruction is ready to issue, "
1040                    "putting it onto the ready list, PC %#x..\n",
1041                    inst->readPC());
1042
1043            readyMiscInsts.push(inst);
1044        }
1045    }
1046}
1047
1048/*
1049 * Caution, this function must not be called prior to tail being updated at
1050 * least once, otherwise it will fail the assertion.  This is because
1051 * instList.begin() actually changes upon the insertion of an element into the
1052 * list when the list is empty.
1053 */
1054template <class Impl>
1055int
1056InstructionQueue<Impl>::countInsts()
1057{
1058    ListIt count_it = cpu->instList.begin();
1059    int total_insts = 0;
1060
1061    if (tail == cpu->instList.end())
1062        return 0;
1063
1064    while (count_it != tail) {
1065        if (!(*count_it)->isIssued()) {
1066            ++total_insts;
1067        }
1068
1069        ++count_it;
1070
1071        assert(count_it != cpu->instList.end());
1072    }
1073
1074    // Need to count the tail iterator as well.
1075    if (count_it != cpu->instList.end() &&
1076        (*count_it) &&
1077        !(*count_it)->isIssued()) {
1078        ++total_insts;
1079    }
1080
1081    return total_insts;
1082}
1083
1084template <class Impl>
1085void
1086InstructionQueue<Impl>::dumpDependGraph()
1087{
1088    DependencyEntry *curr;
1089
1090    for (int i = 0; i < numPhysRegs; ++i)
1091    {
1092        curr = &dependGraph[i];
1093
1094        if (curr->inst) {
1095            cprintf("dependGraph[%i]: producer: %#x consumer: ", i,
1096                    curr->inst->readPC());
1097        } else {
1098            cprintf("dependGraph[%i]: No producer. consumer: ", i);
1099        }
1100
1101        while (curr->next != NULL) {
1102            curr = curr->next;
1103
1104            cprintf("%#x ", curr->inst->readPC());
1105        }
1106
1107        cprintf("\n");
1108    }
1109}
1110
1111template <class Impl>
1112void
1113InstructionQueue<Impl>::dumpLists()
1114{
1115    cprintf("Ready integer list size: %i\n", readyIntInsts.size());
1116
1117    cprintf("Ready float list size: %i\n", readyFloatInsts.size());
1118
1119    cprintf("Ready branch list size: %i\n", readyBranchInsts.size());
1120
1121    cprintf("Ready misc list size: %i\n", readyMiscInsts.size());
1122
1123    cprintf("Squashed list size: %i\n", squashedInsts.size());
1124
1125    cprintf("Non speculative list size: %i\n", nonSpecInsts.size());
1126
1127    non_spec_it_t non_spec_it = nonSpecInsts.begin();
1128
1129    cprintf("Non speculative list: ");
1130
1131    while (non_spec_it != nonSpecInsts.end()) {
1132        cprintf("%#x ", (*non_spec_it).second->readPC());
1133        ++non_spec_it;
1134    }
1135
1136    cprintf("\n");
1137
1138}
1139