2 * Copyright (c) 2004-2006 The Regents of The University of Michigan
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.
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.
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.
41 #include "sim/root.hh"
43 #include "cpu/ozone/inst_queue.hh"
46 InstQueue<Impl>::FUCompletion::FUCompletion(DynInstPtr &_inst,
48 InstQueue<Impl> *iq_ptr)
49 : Event(&mainEventQueue, Stat_Event_Pri),
50 inst(_inst), fuIdx(fu_idx), iqPtr(iq_ptr)
52 this->setFlags(Event::AutoDelete);
57 InstQueue<Impl>::FUCompletion::process()
59 iqPtr->processFUCompletion(inst, fuIdx);
65 InstQueue<Impl>::FUCompletion::description()
67 return "Functional unit completion event";
71 InstQueue<Impl>::InstQueue(Params *params)
72 : dcacheInterface(params->dcacheInterface),
73 // fuPool(params->fuPool),
74 numEntries(params->numIQEntries),
75 totalWidth(params->issueWidth),
76 // numPhysIntRegs(params->numPhysIntRegs),
77 // numPhysFloatRegs(params->numPhysFloatRegs),
78 commitToIEWDelay(params->commitToIEWDelay)
82 // numThreads = params->numberOfThreads;
85 //Initialize thread IQ counts
86 for (int i = 0; i <numThreads; i++) {
90 // Initialize the number of free IQ entries.
91 freeEntries = numEntries;
93 // Set the number of physical registers as the number of int + float
94 // numPhysRegs = numPhysIntRegs + numPhysFloatRegs;
96 // DPRINTF(IQ, "There are %i physical registers.\n", numPhysRegs);
98 //Create an entry for each physical register within the
100 // dependGraph = new DependencyEntry[numPhysRegs];
102 // Resize the register scoreboard.
103 // regScoreboard.resize(numPhysRegs);
105 //Initialize Mem Dependence Units
106 for (int i = 0; i < numThreads; i++) {
107 memDepUnit[i].init(params,i);
108 memDepUnit[i].setIQ(this);
111 // Initialize all the head pointers to point to NULL, and all the
112 // entries as unready.
113 // Note that in actuality, the registers corresponding to the logical
114 // registers start off as ready. However this doesn't matter for the
115 // IQ as the instruction should have been correctly told if those
116 // registers are ready in rename. Thus it can all be initialized as
118 for (int i = 0; i < numPhysRegs; ++i) {
119 dependGraph[i].next = NULL;
120 dependGraph[i].inst = NULL;
121 regScoreboard[i] = false;
124 for (int i = 0; i < numThreads; ++i) {
125 squashedSeqNum[i] = 0;
128 for (int i = 0; i < Num_OpClasses; ++i) {
129 queueOnList[i] = false;
130 readyIt[i] = listOrder.end();
133 string policy = params->smtIQPolicy;
135 //Convert string to lowercase
136 std::transform(policy.begin(), policy.end(), policy.begin(),
137 (int(*)(int)) tolower);
139 //Figure out resource sharing policy
140 if (policy == "dynamic") {
143 //Set Max Entries to Total ROB Capacity
144 for (int i = 0; i < numThreads; i++) {
145 maxEntries[i] = numEntries;
148 } else if (policy == "partitioned") {
149 iqPolicy = Partitioned;
151 //@todo:make work if part_amt doesnt divide evenly.
152 int part_amt = numEntries / numThreads;
154 //Divide ROB up evenly
155 for (int i = 0; i < numThreads; i++) {
156 maxEntries[i] = part_amt;
159 DPRINTF(Fetch, "IQ sharing policy set to Partitioned:"
160 "%i entries per thread.\n",part_amt);
162 } else if (policy == "threshold") {
163 iqPolicy = Threshold;
165 double threshold = (double)params->smtIQThreshold / 100;
167 int thresholdIQ = (int)((double)threshold * numEntries);
169 //Divide up by threshold amount
170 for (int i = 0; i < numThreads; i++) {
171 maxEntries[i] = thresholdIQ;
174 DPRINTF(Fetch, "IQ sharing policy set to Threshold:"
175 "%i entries per thread.\n",thresholdIQ);
177 assert(0 && "Invalid IQ Sharing Policy.Options Are:{Dynamic,"
178 "Partitioned, Threshold}");
183 template <class Impl>
184 InstQueue<Impl>::~InstQueue()
186 // Clear the dependency graph
188 DependencyEntry *curr;
189 DependencyEntry *prev;
191 for (int i = 0; i < numPhysRegs; ++i) {
192 curr = dependGraph[i].next;
195 DependencyEntry::mem_alloc_counter--;
204 if (dependGraph[i].inst) {
205 dependGraph[i].inst = NULL;
208 dependGraph[i].next = NULL;
211 assert(DependencyEntry::mem_alloc_counter == 0);
213 delete [] dependGraph;
217 template <class Impl>
219 InstQueue<Impl>::name() const
221 return cpu->name() + ".iq";
224 template <class Impl>
226 InstQueue<Impl>::regStats()
229 .name(name() + ".iqInstsAdded")
230 .desc("Number of instructions added to the IQ (excludes non-spec)")
231 .prereq(iqInstsAdded);
234 .name(name() + ".iqNonSpecInstsAdded")
235 .desc("Number of non-speculative instructions added to the IQ")
236 .prereq(iqNonSpecInstsAdded);
241 .name(name() + ".iqIntInstsIssued")
242 .desc("Number of integer instructions issued")
243 .prereq(iqIntInstsIssued);
245 // iqFloatInstsAdded;
248 .name(name() + ".iqFloatInstsIssued")
249 .desc("Number of float instructions issued")
250 .prereq(iqFloatInstsIssued);
252 // iqBranchInstsAdded;
255 .name(name() + ".iqBranchInstsIssued")
256 .desc("Number of branch instructions issued")
257 .prereq(iqBranchInstsIssued);
262 .name(name() + ".iqMemInstsIssued")
263 .desc("Number of memory instructions issued")
264 .prereq(iqMemInstsIssued);
269 .name(name() + ".iqMiscInstsIssued")
270 .desc("Number of miscellaneous instructions issued")
271 .prereq(iqMiscInstsIssued);
273 iqSquashedInstsIssued
274 .name(name() + ".iqSquashedInstsIssued")
275 .desc("Number of squashed instructions issued")
276 .prereq(iqSquashedInstsIssued);
278 iqSquashedInstsExamined
279 .name(name() + ".iqSquashedInstsExamined")
280 .desc("Number of squashed instructions iterated over during squash;"
281 " mainly for profiling")
282 .prereq(iqSquashedInstsExamined);
284 iqSquashedOperandsExamined
285 .name(name() + ".iqSquashedOperandsExamined")
286 .desc("Number of squashed operands that are examined and possibly "
287 "removed from graph")
288 .prereq(iqSquashedOperandsExamined);
290 iqSquashedNonSpecRemoved
291 .name(name() + ".iqSquashedNonSpecRemoved")
292 .desc("Number of squashed non-spec instructions that were removed")
293 .prereq(iqSquashedNonSpecRemoved);
295 for ( int i=0; i < numThreads; i++) {
296 // Tell mem dependence unit to reg stats as well.
297 memDepUnit[i].regStats();
302 template <class Impl>
304 InstQueue<Impl>::setActiveThreads(list<unsigned> *at_ptr)
306 DPRINTF(IQ, "Setting active threads list pointer.\n");
307 activeThreads = at_ptr;
310 template <class Impl>
312 InstQueue<Impl>::setIssueToExecuteQueue(TimeBuffer<IssueStruct> *i2e_ptr)
314 DPRINTF(IQ, "Set the issue to execute queue.\n");
315 issueToExecuteQueue = i2e_ptr;
318 template <class Impl>
320 InstQueue<Impl>::setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr)
322 DPRINTF(IQ, "Set the time buffer.\n");
325 fromCommit = timeBuffer->getWire(-commitToIEWDelay);
328 template <class Impl>
330 InstQueue<Impl>::entryAmount(int num_threads)
332 if (iqPolicy == Partitioned) {
333 return numEntries / num_threads;
340 template <class Impl>
342 InstQueue<Impl>::resetEntries()
344 if (iqPolicy != Dynamic || numThreads > 1) {
345 int active_threads = (*activeThreads).size();
347 list<unsigned>::iterator threads = (*activeThreads).begin();
348 list<unsigned>::iterator list_end = (*activeThreads).end();
350 while (threads != list_end) {
351 if (iqPolicy == Partitioned) {
352 maxEntries[*threads++] = numEntries / active_threads;
353 } else if(iqPolicy == Threshold && active_threads == 1) {
354 maxEntries[*threads++] = numEntries;
360 template <class Impl>
362 InstQueue<Impl>::numFreeEntries()
367 template <class Impl>
369 InstQueue<Impl>::numFreeEntries(unsigned tid)
371 return maxEntries[tid] - count[tid];
374 // Might want to do something more complex if it knows how many instructions
375 // will be issued this cycle.
376 template <class Impl>
378 InstQueue<Impl>::isFull()
380 if (freeEntries == 0) {
387 template <class Impl>
389 InstQueue<Impl>::isFull(unsigned tid)
391 if (numFreeEntries(tid) == 0) {
398 template <class Impl>
400 InstQueue<Impl>::hasReadyInsts()
403 if (!listOrder.empty()) {
407 for (int i = 0; i < Num_OpClasses; ++i) {
408 if (!readyInsts[i].empty()) {
415 return readyInsts.empty();
418 template <class Impl>
420 InstQueue<Impl>::insert(DynInstPtr &new_inst)
422 // Make sure the instruction is valid
425 DPRINTF(IQ, "Adding instruction PC %#x to the IQ.\n",
428 // Check if there are any free entries. Panic if there are none.
429 // Might want to have this return a fault in the future instead of
431 assert(freeEntries != 0);
433 instList[new_inst->threadNumber].push_back(new_inst);
435 // Decrease the number of free entries.
438 //Mark Instruction as in IQ
439 // new_inst->setInIQ();
441 // Look through its source registers (physical regs), and mark any
443 addToDependents(new_inst);
445 // Have this instruction set itself as the producer of its destination
447 createDependency(new_inst);
449 // If it's a memory instruction, add it to the memory dependency
451 // if (new_inst->isMemRef()) {
452 // memDepUnit[new_inst->threadNumber].insert(new_inst);
454 // If the instruction is ready then add it to the ready list.
455 addIfReady(new_inst);
461 //Update Thread IQ Count
462 count[new_inst->threadNumber]++;
464 assert(freeEntries == (numEntries - countInsts()));
467 template <class Impl>
469 InstQueue<Impl>::insertNonSpec(DynInstPtr &new_inst)
471 nonSpecInsts[new_inst->seqNum] = new_inst;
473 // @todo: Clean up this code; can do it by setting inst as unable
474 // to issue, then calling normal insert on the inst.
476 // Make sure the instruction is valid
479 DPRINTF(IQ, "Adding instruction PC %#x to the IQ.\n",
482 // Check if there are any free entries. Panic if there are none.
483 // Might want to have this return a fault in the future instead of
485 assert(freeEntries != 0);
487 instList[new_inst->threadNumber].push_back(new_inst);
489 // Decrease the number of free entries.
492 //Mark Instruction as in IQ
493 // new_inst->setInIQ();
495 // Have this instruction set itself as the producer of its destination
497 createDependency(new_inst);
499 // If it's a memory instruction, add it to the memory dependency
501 if (new_inst->isMemRef()) {
502 memDepUnit[new_inst->threadNumber].insertNonSpec(new_inst);
505 ++iqNonSpecInstsAdded;
507 //Update Thread IQ Count
508 count[new_inst->threadNumber]++;
510 assert(freeEntries == (numEntries - countInsts()));
513 template <class Impl>
515 InstQueue<Impl>::advanceTail(DynInstPtr &inst)
517 // Have this instruction set itself as the producer of its destination
519 createDependency(inst);
522 template <class Impl>
524 InstQueue<Impl>::addToOrderList(OpClass op_class)
526 assert(!readyInsts[op_class].empty());
528 ListOrderEntry queue_entry;
530 queue_entry.queueType = op_class;
532 queue_entry.oldestInst = readyInsts[op_class].top()->seqNum;
534 ListOrderIt list_it = listOrder.begin();
535 ListOrderIt list_end_it = listOrder.end();
537 while (list_it != list_end_it) {
538 if ((*list_it).oldestInst > queue_entry.oldestInst) {
545 readyIt[op_class] = listOrder.insert(list_it, queue_entry);
546 queueOnList[op_class] = true;
549 template <class Impl>
551 InstQueue<Impl>::moveToYoungerInst(ListOrderIt list_order_it)
553 // Get iterator of next item on the list
554 // Delete the original iterator
555 // Determine if the next item is either the end of the list or younger
556 // than the new instruction. If so, then add in a new iterator right here.
557 // If not, then move along.
558 ListOrderEntry queue_entry;
559 OpClass op_class = (*list_order_it).queueType;
560 ListOrderIt next_it = list_order_it;
564 queue_entry.queueType = op_class;
565 queue_entry.oldestInst = readyInsts[op_class].top()->seqNum;
567 while (next_it != listOrder.end() &&
568 (*next_it).oldestInst < queue_entry.oldestInst) {
572 readyIt[op_class] = listOrder.insert(next_it, queue_entry);
575 template <class Impl>
577 InstQueue<Impl>::processFUCompletion(DynInstPtr &inst, int fu_idx)
579 // The CPU could have been sleeping until this op completed (*extremely*
580 // long latency op). Wake it if it was. This may be overkill.
583 fuPool->freeUnit(fu_idx);
585 int &size = issueToExecuteQueue->access(0)->size;
587 issueToExecuteQueue->access(0)->insts[size++] = inst;
590 // @todo: Figure out a better way to remove the squashed items from the
591 // lists. Checking the top item of each list to see if it's squashed
592 // wastes time and forces jumps.
593 template <class Impl>
595 InstQueue<Impl>::scheduleReadyInsts()
597 DPRINTF(IQ, "Attempting to schedule ready instructions from "
600 // IssueStruct *i2e_info = issueToExecuteQueue->access(0);
602 // Will need to reorder the list if either a queue is not on the list,
603 // or it has an older instruction than last time.
604 for (int i = 0; i < Num_OpClasses; ++i) {
605 if (!readyInsts[i].empty()) {
606 if (!queueOnList[i]) {
607 addToOrderList(OpClass(i));
608 } else if (readyInsts[i].top()->seqNum <
609 (*readyIt[i]).oldestInst) {
610 listOrder.erase(readyIt[i]);
611 addToOrderList(OpClass(i));
616 // Have iterator to head of the list
617 // While I haven't exceeded bandwidth or reached the end of the list,
618 // Try to get a FU that can do what this op needs.
619 // If successful, change the oldestInst to the new top of the list, put
620 // the queue in the proper place in the list.
621 // Increment the iterator.
622 // This will avoid trying to schedule a certain op class if there are no
623 // FUs that handle it.
624 ListOrderIt order_it = listOrder.begin();
625 ListOrderIt order_end_it = listOrder.end();
626 int total_issued = 0;
627 int exec_queue_slot = i2e_info->size;
629 while (exec_queue_slot < totalWidth && order_it != order_end_it) {
630 OpClass op_class = (*order_it).queueType;
632 assert(!readyInsts[op_class].empty());
634 DynInstPtr issuing_inst = readyInsts[op_class].top();
636 assert(issuing_inst->seqNum == (*order_it).oldestInst);
638 if (issuing_inst->isSquashed()) {
639 readyInsts[op_class].pop();
641 if (!readyInsts[op_class].empty()) {
642 moveToYoungerInst(order_it);
644 readyIt[op_class] = listOrder.end();
645 queueOnList[op_class] = false;
648 listOrder.erase(order_it++);
650 ++iqSquashedInstsIssued;
655 int idx = fuPool->getUnit(op_class);
658 int op_latency = fuPool->getOpLatency(op_class);
660 if (op_latency == 1) {
661 i2e_info->insts[exec_queue_slot++] = issuing_inst;
664 // Add the FU onto the list of FU's to be freed next cycle.
665 fuPool->freeUnit(idx);
667 int issue_latency = fuPool->getIssueLatency(op_class);
669 if (issue_latency > 1) {
670 // Generate completion event for the FU
671 FUCompletion *execution = new FUCompletion(issuing_inst,
674 execution->schedule(curTick + issue_latency - 1);
676 i2e_info->insts[exec_queue_slot++] = issuing_inst;
679 // Add the FU onto the list of FU's to be freed next cycle.
680 fuPool->freeUnit(idx);
684 DPRINTF(IQ, "Thread %i: Issuing instruction PC %#x "
686 issuing_inst->threadNumber, issuing_inst->readPC(),
687 issuing_inst->seqNum);
689 readyInsts[op_class].pop();
691 if (!readyInsts[op_class].empty()) {
692 moveToYoungerInst(order_it);
694 readyIt[op_class] = listOrder.end();
695 queueOnList[op_class] = false;
698 issuing_inst->setIssued();
701 if (!issuing_inst->isMemRef()) {
702 // Memory instructions can not be freed from the IQ until they
705 count[issuing_inst->threadNumber]--;
706 issuing_inst->removeInIQ();
708 memDepUnit[issuing_inst->threadNumber].issue(issuing_inst);
711 listOrder.erase(order_it++);
718 cpu->activityThisCycle();
720 DPRINTF(IQ, "Not able to schedule any instructions.\n");
725 template <class Impl>
727 InstQueue<Impl>::scheduleNonSpec(const InstSeqNum &inst)
729 DPRINTF(IQ, "Marking nonspeculative instruction with sequence "
730 "number %i as ready to execute.\n", inst);
732 NonSpecMapIt inst_it = nonSpecInsts.find(inst);
734 assert(inst_it != nonSpecInsts.end());
736 // unsigned tid = (*inst_it).second->threadNumber;
738 // Mark this instruction as ready to issue.
739 (*inst_it).second->setCanIssue();
741 // Now schedule the instruction.
742 // if (!(*inst_it).second->isMemRef()) {
743 addIfReady((*inst_it).second);
745 // memDepUnit[tid].nonSpecInstReady((*inst_it).second);
748 nonSpecInsts.erase(inst_it);
751 template <class Impl>
753 InstQueue<Impl>::commit(const InstSeqNum &inst, unsigned tid)
755 /*Need to go through each thread??*/
756 DPRINTF(IQ, "[tid:%i]: Committing instructions older than [sn:%i]\n",
759 ListIt iq_it = instList[tid].begin();
761 while (iq_it != instList[tid].end() &&
762 (*iq_it)->seqNum <= inst) {
764 instList[tid].pop_front();
767 assert(freeEntries == (numEntries - countInsts()));
770 template <class Impl>
772 InstQueue<Impl>::wakeDependents(DynInstPtr &completed_inst)
774 DPRINTF(IQ, "Waking dependents of completed instruction.\n");
775 // Look at the physical destination register of the DynInst
776 // and look it up on the dependency graph. Then mark as ready
777 // any instructions within the instruction queue.
779 DependencyEntry *curr;
780 DependencyEntry *prev;
782 // Tell the memory dependence unit to wake any dependents on this
783 // instruction if it is a memory instruction. Also complete the memory
784 // instruction at this point since we know it executed fine.
785 // @todo: Might want to rename "completeMemInst" to
786 // something that indicates that it won't need to be replayed, and call
787 // this earlier. Might not be a big deal.
788 if (completed_inst->isMemRef()) {
789 // memDepUnit[completed_inst->threadNumber].wakeDependents(completed_inst);
790 completeMemInst(completed_inst);
792 completed_inst->wakeDependents();
794 for (int dest_reg_idx = 0;
795 dest_reg_idx < completed_inst->numDestRegs();
798 PhysRegIndex dest_reg =
799 completed_inst->renamedDestRegIdx(dest_reg_idx);
801 // Special case of uniq or control registers. They are not
802 // handled by the IQ and thus have no dependency graph entry.
803 // @todo Figure out a cleaner way to handle this.
804 if (dest_reg >= numPhysRegs) {
808 DPRINTF(IQ, "Waking any dependents on register %i.\n",
811 //Maybe abstract this part into a function.
812 //Go through the dependency chain, marking the registers as ready
813 //within the waiting instructions.
815 curr = dependGraph[dest_reg].next;
818 DPRINTF(IQ, "Waking up a dependent instruction, PC%#x.\n",
819 curr->inst->readPC());
821 // Might want to give more information to the instruction
822 // so that it knows which of its source registers is ready.
823 // However that would mean that the dependency graph entries
824 // would need to hold the src_reg_idx.
825 curr->inst->markSrcRegReady();
827 addIfReady(curr->inst);
829 DependencyEntry::mem_alloc_counter--;
838 // Reset the head node now that all of its dependents have been woken
840 dependGraph[dest_reg].next = NULL;
841 dependGraph[dest_reg].inst = NULL;
843 // Mark the scoreboard as having that register ready.
844 regScoreboard[dest_reg] = true;
849 template <class Impl>
851 InstQueue<Impl>::addReadyMemInst(DynInstPtr &ready_inst)
853 // OpClass op_class = ready_inst->opClass();
855 readyInsts.push(ready_inst);
857 DPRINTF(IQ, "Instruction is ready to issue, putting it onto "
858 "the ready list, PC %#x opclass:%i [sn:%lli].\n",
859 ready_inst->readPC(), ready_inst->opClass(), ready_inst->seqNum);
862 template <class Impl>
864 InstQueue<Impl>::rescheduleMemInst(DynInstPtr &resched_inst)
866 memDepUnit[resched_inst->threadNumber].reschedule(resched_inst);
869 template <class Impl>
871 InstQueue<Impl>::replayMemInst(DynInstPtr &replay_inst)
873 memDepUnit[replay_inst->threadNumber].replay(replay_inst);
876 template <class Impl>
878 InstQueue<Impl>::completeMemInst(DynInstPtr &completed_inst)
880 int tid = completed_inst->threadNumber;
882 DPRINTF(IQ, "Completing mem instruction PC:%#x [sn:%lli]\n",
883 completed_inst->readPC(), completed_inst->seqNum);
887 // completed_inst->memOpDone = true;
889 // memDepUnit[tid].completed(completed_inst);
894 template <class Impl>
896 InstQueue<Impl>::violation(DynInstPtr &store,
897 DynInstPtr &faulting_load)
899 memDepUnit[store->threadNumber].violation(store, faulting_load);
902 template <class Impl>
904 InstQueue<Impl>::squash(unsigned tid)
906 DPRINTF(IQ, "[tid:%i]: Starting to squash instructions in "
909 // Read instruction sequence number of last instruction out of the
911 // squashedSeqNum[tid] = fromCommit->commitInfo[tid].doneSeqNum;
913 // Setup the squash iterator to point to the tail.
914 squashIt[tid] = instList[tid].end();
917 // Call doSquash if there are insts in the IQ
918 if (count[tid] > 0) {
922 // Also tell the memory dependence unit to squash.
923 // memDepUnit[tid].squash(squashedSeqNum[tid], tid);
926 template <class Impl>
928 InstQueue<Impl>::doSquash(unsigned tid)
930 // Make sure the squashed sequence number is valid.
931 assert(squashedSeqNum[tid] != 0);
933 DPRINTF(IQ, "[tid:%i]: Squashing until sequence number %i!\n",
934 tid, squashedSeqNum[tid]);
936 // Squash any instructions younger than the squashed sequence number
938 while (squashIt[tid] != instList[tid].end() &&
939 (*squashIt[tid])->seqNum > squashedSeqNum[tid]) {
941 DynInstPtr squashed_inst = (*squashIt[tid]);
943 // Only handle the instruction if it actually is in the IQ and
944 // hasn't already been squashed in the IQ.
945 if (squashed_inst->threadNumber != tid ||
946 squashed_inst->isSquashedInIQ()) {
951 if (!squashed_inst->isIssued() ||
952 (squashed_inst->isMemRef()/* &&
953 !squashed_inst->memOpDone*/)) {
955 // Remove the instruction from the dependency list.
956 if (!squashed_inst->isNonSpeculative()) {
958 for (int src_reg_idx = 0;
959 src_reg_idx < squashed_inst->numSrcRegs();
962 PhysRegIndex src_reg =
963 squashed_inst->renamedSrcRegIdx(src_reg_idx);
965 // Only remove it from the dependency graph if it was
966 // placed there in the first place.
967 // HACK: This assumes that instructions woken up from the
968 // dependency chain aren't informed that a specific src
969 // register has become ready. This may not always be true
971 // Instead of doing a linked list traversal, we can just
972 // remove these squashed instructions either at issue time,
973 // or when the register is overwritten. The only downside
974 // to this is it leaves more room for error.
976 if (!squashed_inst->isReadySrcRegIdx(src_reg_idx) &&
977 src_reg < numPhysRegs) {
978 dependGraph[src_reg].remove(squashed_inst);
982 ++iqSquashedOperandsExamined;
985 // Might want to remove producers as well.
987 nonSpecInsts[squashed_inst->seqNum] = NULL;
989 nonSpecInsts.erase(squashed_inst->seqNum);
991 ++iqSquashedNonSpecRemoved;
994 // Might want to also clear out the head of the dependency graph.
996 // Mark it as squashed within the IQ.
997 squashed_inst->setSquashedInIQ();
999 // @todo: Remove this hack where several statuses are set so the
1000 // inst will flow through the rest of the pipeline.
1001 squashed_inst->setIssued();
1002 squashed_inst->setCanCommit();
1003 // squashed_inst->removeInIQ();
1005 //Update Thread IQ Count
1006 count[squashed_inst->threadNumber]--;
1010 if (numThreads > 1) {
1011 DPRINTF(IQ, "[tid:%i]: Instruction PC %#x squashed.\n",
1012 tid, squashed_inst->readPC());
1014 DPRINTF(IQ, "Instruction PC %#x squashed.\n",
1015 squashed_inst->readPC());
1020 ++iqSquashedInstsExamined;
1024 template <class Impl>
1026 InstQueue<Impl>::DependencyEntry::insert(DynInstPtr &new_inst)
1028 //Add this new, dependent instruction at the head of the dependency
1031 // First create the entry that will be added to the head of the
1032 // dependency chain.
1033 DependencyEntry *new_entry = new DependencyEntry;
1034 new_entry->next = this->next;
1035 new_entry->inst = new_inst;
1037 // Then actually add it to the chain.
1038 this->next = new_entry;
1040 ++mem_alloc_counter;
1043 template <class Impl>
1045 InstQueue<Impl>::DependencyEntry::remove(DynInstPtr &inst_to_remove)
1047 DependencyEntry *prev = this;
1048 DependencyEntry *curr = this->next;
1050 // Make sure curr isn't NULL. Because this instruction is being
1051 // removed from a dependency list, it must have been placed there at
1052 // an earlier time. The dependency chain should not be empty,
1053 // unless the instruction dependent upon it is already ready.
1058 // Find the instruction to remove within the dependency linked list.
1059 while (curr->inst != inst_to_remove) {
1063 assert(curr != NULL);
1066 // Now remove this instruction from the list.
1067 prev->next = curr->next;
1069 --mem_alloc_counter;
1071 // Could push this off to the destructor of DependencyEntry
1077 template <class Impl>
1079 InstQueue<Impl>::addToDependents(DynInstPtr &new_inst)
1081 // Loop through the instruction's source registers, adding
1082 // them to the dependency list if they are not ready.
1083 int8_t total_src_regs = new_inst->numSrcRegs();
1084 bool return_val = false;
1086 for (int src_reg_idx = 0;
1087 src_reg_idx < total_src_regs;
1090 // Only add it to the dependency graph if it's not ready.
1091 if (!new_inst->isReadySrcRegIdx(src_reg_idx)) {
1092 PhysRegIndex src_reg = new_inst->renamedSrcRegIdx(src_reg_idx);
1094 // Check the IQ's scoreboard to make sure the register
1095 // hasn't become ready while the instruction was in flight
1096 // between stages. Only if it really isn't ready should
1097 // it be added to the dependency graph.
1098 if (src_reg >= numPhysRegs) {
1100 } else if (regScoreboard[src_reg] == false) {
1101 DPRINTF(IQ, "Instruction PC %#x has src reg %i that "
1102 "is being added to the dependency chain.\n",
1103 new_inst->readPC(), src_reg);
1105 dependGraph[src_reg].insert(new_inst);
1107 // Change the return value to indicate that something
1108 // was added to the dependency graph.
1111 DPRINTF(IQ, "Instruction PC %#x has src reg %i that "
1112 "became ready before it reached the IQ.\n",
1113 new_inst->readPC(), src_reg);
1114 // Mark a register ready within the instruction.
1115 new_inst->markSrcRegReady();
1123 template <class Impl>
1125 InstQueue<Impl>::createDependency(DynInstPtr &new_inst)
1127 //Actually nothing really needs to be marked when an
1128 //instruction becomes the producer of a register's value,
1129 //but for convenience a ptr to the producing instruction will
1130 //be placed in the head node of the dependency links.
1131 int8_t total_dest_regs = new_inst->numDestRegs();
1133 for (int dest_reg_idx = 0;
1134 dest_reg_idx < total_dest_regs;
1137 PhysRegIndex dest_reg = new_inst->renamedDestRegIdx(dest_reg_idx);
1139 // Instructions that use the misc regs will have a reg number
1140 // higher than the normal physical registers. In this case these
1141 // registers are not renamed, and there is no need to track
1142 // dependencies as these instructions must be executed at commit.
1143 if (dest_reg >= numPhysRegs) {
1147 if (dependGraph[dest_reg].next) {
1149 panic("Dependency graph %i not empty!", dest_reg);
1152 dependGraph[dest_reg].inst = new_inst;
1154 // Mark the scoreboard to say it's not yet ready.
1155 regScoreboard[dest_reg] = false;
1159 template <class Impl>
1161 InstQueue<Impl>::addIfReady(DynInstPtr &inst)
1163 //If the instruction now has all of its source registers
1164 // available, then add it to the list of ready instructions.
1165 if (inst->readyToIssue()) {
1167 //Add the instruction to the proper ready list.
1168 if (inst->isMemRef()) {
1170 DPRINTF(IQ, "Checking if memory instruction can issue.\n");
1172 // Message to the mem dependence unit that this instruction has
1173 // its registers ready.
1175 // memDepUnit[inst->threadNumber].regsReady(inst);
1180 // OpClass op_class = inst->opClass();
1182 DPRINTF(IQ, "Instruction is ready to issue, putting it onto "
1183 "the ready list, PC %#x opclass:%i [sn:%lli].\n",
1184 inst->readPC(), inst->opClass(), inst->seqNum);
1186 readyInsts.push(inst);
1190 template <class Impl>
1192 InstQueue<Impl>::countInsts()
1194 //ksewell:This works but definitely could use a cleaner write
1195 //with a more intuitive way of counting. Right now it's
1196 //just brute force ....
1199 int total_insts = 0;
1201 for (int i = 0; i < numThreads; ++i) {
1202 ListIt count_it = instList[i].begin();
1204 while (count_it != instList[i].end()) {
1205 if (!(*count_it)->isSquashed() && !(*count_it)->isSquashedInIQ()) {
1206 if (!(*count_it)->isIssued()) {
1208 } else if ((*count_it)->isMemRef() &&
1209 !(*count_it)->memOpDone) {
1210 // Loads that have not been marked as executed still count
1211 // towards the total instructions.
1222 return numEntries - freeEntries;
1226 template <class Impl>
1228 InstQueue<Impl>::dumpDependGraph()
1230 DependencyEntry *curr;
1232 for (int i = 0; i < numPhysRegs; ++i)
1234 curr = &dependGraph[i];
1237 cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ",
1238 i, curr->inst->readPC(), curr->inst->seqNum);
1240 cprintf("dependGraph[%i]: No producer. consumer: ", i);
1243 while (curr->next != NULL) {
1246 cprintf("%#x [sn:%lli] ",
1247 curr->inst->readPC(), curr->inst->seqNum);
1254 template <class Impl>
1256 InstQueue<Impl>::dumpLists()
1258 for (int i = 0; i < Num_OpClasses; ++i) {
1259 cprintf("Ready list %i size: %i\n", i, readyInsts.size());
1264 cprintf("Non speculative list size: %i\n", nonSpecInsts.size());
1266 NonSpecMapIt non_spec_it = nonSpecInsts.begin();
1267 NonSpecMapIt non_spec_end_it = nonSpecInsts.end();
1269 cprintf("Non speculative list: ");
1271 while (non_spec_it != non_spec_end_it) {
1272 cprintf("%#x [sn:%lli]", (*non_spec_it).second->readPC(),
1273 (*non_spec_it).second->seqNum);
1279 ListOrderIt list_order_it = listOrder.begin();
1280 ListOrderIt list_order_end_it = listOrder.end();
1283 cprintf("List order: ");
1285 while (list_order_it != list_order_end_it) {
1286 cprintf("%i OpClass:%i [sn:%lli] ", i, (*list_order_it).queueType,
1287 (*list_order_it).oldestInst);
1297 template <class Impl>
1299 InstQueue<Impl>::dumpInsts()
1301 for (int i = 0; i < numThreads; ++i) {
1303 // int valid_num = 0;
1305 ListIt inst_list_it = instList[i].begin();
1307 while (inst_list_it != instList[i].end())
1309 cprintf("Instruction:%i\n",
1311 if (!(*inst_list_it)->isSquashed()) {
1312 if (!(*inst_list_it)->isIssued()) {
1314 cprintf("Count:%i\n", valid_num);
1315 } else if ((*inst_list_it)->isMemRef() &&
1316 !(*inst_list_it)->memOpDone) {
1317 // Loads that have not been marked as executed still count
1318 // towards the total instructions.
1320 cprintf("Count:%i\n", valid_num);
1324 cprintf("PC:%#x\n[sn:%lli]\n[tid:%i]\n"
1325 "Issued:%i\nSquashed:%i\n",
1326 (*inst_list_it)->readPC(),
1327 (*inst_list_it)->seqNum,
1328 (*inst_list_it)->threadNumber,
1329 (*inst_list_it)->isIssued(),
1330 (*inst_list_it)->isSquashed());
1332 if ((*inst_list_it)->isMemRef()) {
1333 cprintf("MemOpDone:%i\n", (*inst_list_it)->memOpDone);