dep_graph.hh revision 2674:6d4afef73a20
12SN/A 27338SAli.Saidi@ARM.com#ifndef __CPU_O3_DEP_GRAPH_HH__ 37338SAli.Saidi@ARM.com#define __CPU_O3_DEP_GRAPH_HH__ 47338SAli.Saidi@ARM.com 57338SAli.Saidi@ARM.com#include "cpu/o3/comm.hh" 67338SAli.Saidi@ARM.com 77338SAli.Saidi@ARM.com/** Node in a linked list. */ 87338SAli.Saidi@ARM.comtemplate <class DynInstPtr> 97338SAli.Saidi@ARM.comclass DependencyEntry 107338SAli.Saidi@ARM.com{ 117338SAli.Saidi@ARM.com public: 127338SAli.Saidi@ARM.com DependencyEntry() 137338SAli.Saidi@ARM.com : inst(NULL), next(NULL) 141762SN/A { } 152SN/A 162SN/A DynInstPtr inst; 172SN/A //Might want to include data about what arch. register the 182SN/A //dependence is waiting on. 192SN/A DependencyEntry<DynInstPtr> *next; 202SN/A}; 212SN/A 222SN/A/** Array of linked list that maintains the dependencies between 232SN/A * producing instructions and consuming instructions. Each linked 242SN/A * list represents a single physical register, having the future 252SN/A * producer of the register's value, and all consumers waiting on that 262SN/A * value on the list. The head node of each linked list represents 272SN/A * the producing instruction of that register. Instructions are put 282SN/A * on the list upon reaching the IQ, and are removed from the list 292SN/A * either when the producer completes, or the instruction is squashed. 302SN/A*/ 312SN/Atemplate <class DynInstPtr> 322SN/Aclass DependencyGraph 332SN/A{ 342SN/A public: 352SN/A typedef DependencyEntry<DynInstPtr> DepEntry; 362SN/A 372SN/A /** Default construction. Must call resize() prior to use. */ 382SN/A DependencyGraph() 392665Ssaidi@eecs.umich.edu : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0) 402665Ssaidi@eecs.umich.edu { } 412SN/A 422SN/A /** Resize the dependency graph to have num_entries registers. */ 436216Snate@binkert.org void resize(int num_entries); 448779Sgblack@eecs.umich.edu 458779Sgblack@eecs.umich.edu /** Clears all of the linked lists. */ 468779Sgblack@eecs.umich.edu void reset(); 472439SN/A 488779Sgblack@eecs.umich.edu /** Inserts an instruction to be dependent on the given index. */ 498229Snate@binkert.org void insert(PhysRegIndex idx, DynInstPtr &new_inst); 506216Snate@binkert.org 51146SN/A /** Sets the producing instruction of a given register. */ 52146SN/A void setInst(PhysRegIndex idx, DynInstPtr &new_inst) 53146SN/A { dependGraph[idx].inst = new_inst; } 54146SN/A 55146SN/A /** Clears the producing instruction. */ 56146SN/A void clearInst(PhysRegIndex idx) 576216Snate@binkert.org { dependGraph[idx].inst = NULL; } 586658Snate@binkert.org 598229Snate@binkert.org /** Removes an instruction from a single linked list. */ 601717SN/A void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove); 61146SN/A 621977SN/A /** Removes and returns the newest dependent of a specific register. */ 632683Sktlim@umich.edu DynInstPtr pop(PhysRegIndex idx); 641717SN/A 65146SN/A /** Checks if there are any dependents on a specific register. */ 662683Sktlim@umich.edu bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; } 678232Snate@binkert.org 688232Snate@binkert.org /** Debugging function to dump out the dependency graph. 698232Snate@binkert.org */ 708779Sgblack@eecs.umich.edu void dump(); 713348Sbinkertn@umich.edu 726105Ssteve.reinhardt@amd.com private: 736216Snate@binkert.org /** Array of linked lists. Each linked list is a list of all the 742036SN/A * instructions that depend upon a given register. The actual 75146SN/A * register's index is used to index into the graph; ie all 768793Sgblack@eecs.umich.edu * instructions in flight that are dependent upon r34 will be 7756SN/A * in the linked list of dependGraph[34]. 7856SN/A */ 79695SN/A DepEntry *dependGraph; 802901Ssaidi@eecs.umich.edu 812SN/A /** Number of linked lists; identical to the number of registers. */ 822SN/A int numEntries; 832449SN/A 841355SN/A // Debug variable, remove when done testing. 855529Snate@binkert.org unsigned memAllocCounter; 864495Sacolyte@umich.edu 87224SN/A public: 888793Sgblack@eecs.umich.edu // Debug variable, remove when done testing. 898793Sgblack@eecs.umich.edu uint64_t nodesTraversed; 908793Sgblack@eecs.umich.edu // Debug variable, remove when done testing. 918793Sgblack@eecs.umich.edu uint64_t nodesRemoved; 928793Sgblack@eecs.umich.edu}; 932SN/A 946029Ssteve.reinhardt@amd.comtemplate <class DynInstPtr> 952672Sktlim@umich.eduvoid 962683Sktlim@umich.eduDependencyGraph<DynInstPtr>::resize(int num_entries) 972SN/A{ 982SN/A numEntries = num_entries; 99334SN/A dependGraph = new DepEntry[numEntries]; 100140SN/A} 101334SN/A 1022SN/Atemplate <class DynInstPtr> 1032SN/Avoid 1042SN/ADependencyGraph<DynInstPtr>::reset() 1052680Sktlim@umich.edu{ 1064377Sgblack@eecs.umich.edu // Clear the dependency graph 1075169Ssaidi@eecs.umich.edu DepEntry *curr; 1084377Sgblack@eecs.umich.edu DepEntry *prev; 1094377Sgblack@eecs.umich.edu 1102SN/A for (int i = 0; i < numEntries; ++i) { 1112SN/A curr = dependGraph[i].next; 1122623SN/A 1132SN/A while (curr) { 1142SN/A memAllocCounter--; 1152SN/A 116180SN/A prev = curr; 1172623SN/A curr = prev->next; 118393SN/A prev->inst = NULL; 119393SN/A 120393SN/A delete prev; 121393SN/A } 122384SN/A 123384SN/A if (dependGraph[i].inst) { 124393SN/A dependGraph[i].inst = NULL; 1252623SN/A } 126393SN/A 127393SN/A dependGraph[i].next = NULL; 128393SN/A } 129393SN/A} 130384SN/A 131189SN/Atemplate <class DynInstPtr> 132189SN/Avoid 1332623SN/ADependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst) 1342SN/A{ 135729SN/A //Add this new, dependent instruction at the head of the dependency 136334SN/A //chain. 1372SN/A 1382SN/A // First create the entry that will be added to the head of the 1392SN/A // dependency chain. 1402SN/A DepEntry *new_entry = new DepEntry; 1412SN/A new_entry->next = dependGraph[idx].next; 1422SN/A new_entry->inst = new_inst; 1432SN/A 1447897Shestness@cs.utexas.edu // Then actually add it to the chain. 1457897Shestness@cs.utexas.edu dependGraph[idx].next = new_entry; 1467897Shestness@cs.utexas.edu 1477897Shestness@cs.utexas.edu ++memAllocCounter; 1487897Shestness@cs.utexas.edu} 1497897Shestness@cs.utexas.edu 1507897Shestness@cs.utexas.edu 1517897Shestness@cs.utexas.edutemplate <class DynInstPtr> 1527897Shestness@cs.utexas.eduvoid 1537897Shestness@cs.utexas.eduDependencyGraph<DynInstPtr>::remove(PhysRegIndex idx, 1547897Shestness@cs.utexas.edu DynInstPtr &inst_to_remove) 1557897Shestness@cs.utexas.edu{ 1567897Shestness@cs.utexas.edu DepEntry *prev = &dependGraph[idx]; 1577897Shestness@cs.utexas.edu DepEntry *curr = dependGraph[idx].next; 1587897Shestness@cs.utexas.edu 1597897Shestness@cs.utexas.edu // Make sure curr isn't NULL. Because this instruction is being 1607897Shestness@cs.utexas.edu // removed from a dependency list, it must have been placed there at 1617897Shestness@cs.utexas.edu // an earlier time. The dependency chain should not be empty, 1627897Shestness@cs.utexas.edu // unless the instruction dependent upon it is already ready. 1637897Shestness@cs.utexas.edu if (curr == NULL) { 1647897Shestness@cs.utexas.edu return; 1657897Shestness@cs.utexas.edu } 1667897Shestness@cs.utexas.edu 1677897Shestness@cs.utexas.edu nodesRemoved++; 1687897Shestness@cs.utexas.edu 1697897Shestness@cs.utexas.edu // Find the instruction to remove within the dependency linked list. 1707897Shestness@cs.utexas.edu while (curr->inst != inst_to_remove) { 1717897Shestness@cs.utexas.edu prev = curr; 1727897Shestness@cs.utexas.edu curr = curr->next; 1737897Shestness@cs.utexas.edu nodesTraversed++; 1747897Shestness@cs.utexas.edu 1757897Shestness@cs.utexas.edu assert(curr != NULL); 1767897Shestness@cs.utexas.edu } 1777897Shestness@cs.utexas.edu 1787897Shestness@cs.utexas.edu // Now remove this instruction from the list. 1797897Shestness@cs.utexas.edu prev->next = curr->next; 1807897Shestness@cs.utexas.edu 1817897Shestness@cs.utexas.edu --memAllocCounter; 1827897Shestness@cs.utexas.edu 1837897Shestness@cs.utexas.edu // Could push this off to the destructor of DependencyEntry 1847897Shestness@cs.utexas.edu curr->inst = NULL; 1857897Shestness@cs.utexas.edu 1867897Shestness@cs.utexas.edu delete curr; 1877897Shestness@cs.utexas.edu} 1887897Shestness@cs.utexas.edu 1897897Shestness@cs.utexas.edutemplate <class DynInstPtr> 1907897Shestness@cs.utexas.eduDynInstPtr 1917897Shestness@cs.utexas.eduDependencyGraph<DynInstPtr>::pop(PhysRegIndex idx) 1927897Shestness@cs.utexas.edu{ 1937897Shestness@cs.utexas.edu DepEntry *node; 1942SN/A node = dependGraph[idx].next; 1957897Shestness@cs.utexas.edu DynInstPtr inst = NULL; 1967897Shestness@cs.utexas.edu if (node) { 1977897Shestness@cs.utexas.edu inst = node->inst; 1987897Shestness@cs.utexas.edu dependGraph[idx].next = node->next; 1997897Shestness@cs.utexas.edu node->inst = NULL; 2007897Shestness@cs.utexas.edu memAllocCounter--; 2017897Shestness@cs.utexas.edu delete node; 2027897Shestness@cs.utexas.edu } 2037897Shestness@cs.utexas.edu return inst; 2047897Shestness@cs.utexas.edu} 2057897Shestness@cs.utexas.edu 2067897Shestness@cs.utexas.edutemplate <class DynInstPtr> 2072SN/Avoid 2082SN/ADependencyGraph<DynInstPtr>::dump() 2091001SN/A{ 2101001SN/A DepEntry *curr; 2111001SN/A 2121001SN/A for (int i = 0; i < numEntries; ++i) 2131001SN/A { 2142SN/A curr = &dependGraph[i]; 2152SN/A 2162SN/A if (curr->inst) { 2172SN/A cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ", 2182SN/A i, curr->inst->readPC(), curr->inst->seqNum); 2197897Shestness@cs.utexas.edu } else { 2207897Shestness@cs.utexas.edu cprintf("dependGraph[%i]: No producer. consumer: ", i); 2217897Shestness@cs.utexas.edu } 2227897Shestness@cs.utexas.edu 2237897Shestness@cs.utexas.edu while (curr->next != NULL) { 2247897Shestness@cs.utexas.edu curr = curr->next; 2257897Shestness@cs.utexas.edu 2267897Shestness@cs.utexas.edu cprintf("%#x [sn:%lli] ", 2277897Shestness@cs.utexas.edu curr->inst->readPC(), curr->inst->seqNum); 2287897Shestness@cs.utexas.edu } 2292SN/A 2302SN/A cprintf("\n"); 2312SN/A } 2322SN/A cprintf("memAllocCounter: %i\n", memAllocCounter); 2332SN/A} 2342SN/A 2352SN/A#endif // __CPU_O3_DEP_GRAPH_HH__ 2362SN/A