/* * Copyright (c) 2012 ARM Limited * All rights reserved * * The license below extends only to copyright in the software and shall * not be construed as granting a license to any other intellectual * property including but not limited to intellectual property relating * to a hardware implementation of the functionality of the software * licensed hereunder. You may use the software subject to the license * terms below provided that you ensure that this notice is replicated * unmodified and in its entirety in all distributions of the software, * modified or unmodified, in source code or in binary form. * * Copyright (c) 2006 The Regents of The University of Michigan * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions are * met: redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer; * redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution; * neither the name of the copyright holders nor the names of its * contributors may be used to endorse or promote products derived from * this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * Authors: Kevin Lim */ #ifndef __CPU_O3_DEP_GRAPH_HH__ #define __CPU_O3_DEP_GRAPH_HH__ #include "cpu/o3/comm.hh" /** Node in a linked list. */ template class DependencyEntry { public: DependencyEntry() : inst(NULL), next(NULL) { } DynInstPtr inst; //Might want to include data about what arch. register the //dependence is waiting on. DependencyEntry *next; }; /** Array of linked list that maintains the dependencies between * producing instructions and consuming instructions. Each linked * list represents a single physical register, having the future * producer of the register's value, and all consumers waiting on that * value on the list. The head node of each linked list represents * the producing instruction of that register. Instructions are put * on the list upon reaching the IQ, and are removed from the list * either when the producer completes, or the instruction is squashed. */ template class DependencyGraph { public: typedef DependencyEntry DepEntry; /** Default construction. Must call resize() prior to use. */ DependencyGraph() : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0) { } ~DependencyGraph(); /** Resize the dependency graph to have num_entries registers. */ void resize(int num_entries); /** Clears all of the linked lists. */ void reset(); /** Inserts an instruction to be dependent on the given index. */ void insert(PhysRegIndex idx, const DynInstPtr &new_inst); /** Sets the producing instruction of a given register. */ void setInst(PhysRegIndex idx, const DynInstPtr &new_inst) { dependGraph[idx].inst = new_inst; } /** Clears the producing instruction. */ void clearInst(PhysRegIndex idx) { dependGraph[idx].inst = NULL; } /** Removes an instruction from a single linked list. */ void remove(PhysRegIndex idx, const DynInstPtr &inst_to_remove); /** Removes and returns the newest dependent of a specific register. */ DynInstPtr pop(PhysRegIndex idx); /** Checks if the entire dependency graph is empty. */ bool empty() const; /** Checks if there are any dependents on a specific register. */ bool empty(PhysRegIndex idx) const { return !dependGraph[idx].next; } /** Debugging function to dump out the dependency graph. */ void dump(); private: /** Array of linked lists. Each linked list is a list of all the * instructions that depend upon a given register. The actual * register's index is used to index into the graph; ie all * instructions in flight that are dependent upon r34 will be * in the linked list of dependGraph[34]. */ std::vector dependGraph; /** Number of linked lists; identical to the number of registers. */ int numEntries; // Debug variable, remove when done testing. unsigned memAllocCounter; public: // Debug variable, remove when done testing. uint64_t nodesTraversed; // Debug variable, remove when done testing. uint64_t nodesRemoved; }; template DependencyGraph::~DependencyGraph() { } template void DependencyGraph::resize(int num_entries) { numEntries = num_entries; dependGraph.resize(numEntries); } template void DependencyGraph::reset() { // Clear the dependency graph DepEntry *curr; DepEntry *prev; for (int i = 0; i < numEntries; ++i) { curr = dependGraph[i].next; while (curr) { memAllocCounter--; prev = curr; curr = prev->next; prev->inst = NULL; delete prev; } if (dependGraph[i].inst) { dependGraph[i].inst = NULL; } dependGraph[i].next = NULL; } } template void DependencyGraph::insert(PhysRegIndex idx, const DynInstPtr &new_inst) { //Add this new, dependent instruction at the head of the dependency //chain. // First create the entry that will be added to the head of the // dependency chain. DepEntry *new_entry = new DepEntry; new_entry->next = dependGraph[idx].next; new_entry->inst = new_inst; // Then actually add it to the chain. dependGraph[idx].next = new_entry; ++memAllocCounter; } template void DependencyGraph::remove(PhysRegIndex idx, const DynInstPtr &inst_to_remove) { DepEntry *prev = &dependGraph[idx]; DepEntry *curr = dependGraph[idx].next; // Make sure curr isn't NULL. Because this instruction is being // removed from a dependency list, it must have been placed there at // an earlier time. The dependency chain should not be empty, // unless the instruction dependent upon it is already ready. if (curr == NULL) { return; } nodesRemoved++; // Find the instruction to remove within the dependency linked list. while (curr->inst != inst_to_remove) { prev = curr; curr = curr->next; nodesTraversed++; assert(curr != NULL); } // Now remove this instruction from the list. prev->next = curr->next; --memAllocCounter; // Could push this off to the destructor of DependencyEntry curr->inst = NULL; delete curr; } template DynInstPtr DependencyGraph::pop(PhysRegIndex idx) { DepEntry *node; node = dependGraph[idx].next; DynInstPtr inst = NULL; if (node) { inst = node->inst; dependGraph[idx].next = node->next; node->inst = NULL; memAllocCounter--; delete node; } return inst; } template bool DependencyGraph::empty() const { for (int i = 0; i < numEntries; ++i) { if (!empty(i)) return false; } return true; } template void DependencyGraph::dump() { DepEntry *curr; for (int i = 0; i < numEntries; ++i) { curr = &dependGraph[i]; if (curr->inst) { cprintf("dependGraph[%i]: producer: %s [sn:%lli] consumer: ", i, curr->inst->pcState(), curr->inst->seqNum); } else { cprintf("dependGraph[%i]: No producer. consumer: ", i); } while (curr->next != NULL) { curr = curr->next; cprintf("%s [sn:%lli] ", curr->inst->pcState(), curr->inst->seqNum); } cprintf("\n"); } cprintf("memAllocCounter: %i\n", memAllocCounter); } #endif // __CPU_O3_DEP_GRAPH_HH__