dep_graph.hh revision 2326
12686Sksewell@umich.edu 22100SN/A#ifndef __CPU_O3_DEP_GRAPH_HH__ 35254Sksewell@umich.edu#define __CPU_O3_DEP_GRAPH_HH__ 45254Sksewell@umich.edu 55254Sksewell@umich.edu#include "cpu/o3/comm.hh" 65254Sksewell@umich.edu 75254Sksewell@umich.edutemplate <class DynInstPtr> 85254Sksewell@umich.educlass DependencyEntry 95254Sksewell@umich.edu{ 105254Sksewell@umich.edu public: 115254Sksewell@umich.edu DependencyEntry() 125254Sksewell@umich.edu : inst(NULL), next(NULL) 135254Sksewell@umich.edu { } 145254Sksewell@umich.edu 155254Sksewell@umich.edu DynInstPtr inst; 165254Sksewell@umich.edu //Might want to include data about what arch. register the 175254Sksewell@umich.edu //dependence is waiting on. 185254Sksewell@umich.edu DependencyEntry<DynInstPtr> *next; 195254Sksewell@umich.edu}; 205254Sksewell@umich.edu 215254Sksewell@umich.edutemplate <class DynInstPtr> 225254Sksewell@umich.educlass DependencyGraph 235254Sksewell@umich.edu{ 245254Sksewell@umich.edu public: 255254Sksewell@umich.edu typedef DependencyEntry<DynInstPtr> DepEntry; 265254Sksewell@umich.edu 275254Sksewell@umich.edu DependencyGraph() 285254Sksewell@umich.edu : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0) 295254Sksewell@umich.edu { } 305254Sksewell@umich.edu 315254Sksewell@umich.edu void resize(int num_entries); 322706Sksewell@umich.edu 332022SN/A void reset(); 342022SN/A 352043SN/A void insert(PhysRegIndex idx, DynInstPtr &new_inst); 362024SN/A 372024SN/A void setInst(PhysRegIndex idx, DynInstPtr &new_inst) 382043SN/A { dependGraph[idx].inst = new_inst; } 392686Sksewell@umich.edu 404661Sksewell@umich.edu void clearInst(PhysRegIndex idx) 412022SN/A { dependGraph[idx].inst = NULL; } 422083SN/A 432686Sksewell@umich.edu void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove); 442101SN/A 452043SN/A DynInstPtr pop(PhysRegIndex idx); 462043SN/A 472101SN/A bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; } 482101SN/A 496384Sgblack@eecs.umich.edu /** Debugging function to dump out the dependency graph. 506384Sgblack@eecs.umich.edu */ 516384Sgblack@eecs.umich.edu void dump(); 526384Sgblack@eecs.umich.edu 536384Sgblack@eecs.umich.edu private: 546384Sgblack@eecs.umich.edu /** Array of linked lists. Each linked list is a list of all the 552101SN/A * instructions that depend upon a given register. The actual 562101SN/A * register's index is used to index into the graph; ie all 572101SN/A * instructions in flight that are dependent upon r34 will be 582046SN/A * in the linked list of dependGraph[34]. 592686Sksewell@umich.edu */ 602686Sksewell@umich.edu DepEntry *dependGraph; 612686Sksewell@umich.edu 622470SN/A int numEntries; 632686Sksewell@umich.edu 644661Sksewell@umich.edu // Debug variable, remove when done testing. 655222Sksewell@umich.edu unsigned memAllocCounter; 665222Sksewell@umich.edu 672686Sksewell@umich.edu public: 688588Sgblack@eecs.umich.edu uint64_t nodesTraversed; 692470SN/A uint64_t nodesRemoved; 702241SN/A}; 712101SN/A 722495SN/Atemplate <class DynInstPtr> 732495SN/Avoid 748588Sgblack@eecs.umich.eduDependencyGraph<DynInstPtr>::resize(int num_entries) 752101SN/A{ 766384Sgblack@eecs.umich.edu numEntries = num_entries; 776384Sgblack@eecs.umich.edu dependGraph = new DepEntry[numEntries]; 786384Sgblack@eecs.umich.edu} 798588Sgblack@eecs.umich.edu 806384Sgblack@eecs.umich.edutemplate <class DynInstPtr> 812495SN/Avoid 822101SN/ADependencyGraph<DynInstPtr>::reset() 832101SN/A{ 842495SN/A // Clear the dependency graph 852495SN/A DepEntry *curr; 862495SN/A DepEntry *prev; 872495SN/A 882495SN/A for (int i = 0; i < numEntries; ++i) { 892495SN/A curr = dependGraph[i].next; 902495SN/A 912495SN/A while (curr) { 922495SN/A memAllocCounter--; 932495SN/A 942495SN/A prev = curr; 952495SN/A curr = prev->next; 962495SN/A prev->inst = NULL; 972101SN/A 988588Sgblack@eecs.umich.edu delete prev; 992101SN/A } 1002101SN/A 1018588Sgblack@eecs.umich.edu if (dependGraph[i].inst) { 1022101SN/A dependGraph[i].inst = NULL; 1036384Sgblack@eecs.umich.edu } 1046384Sgblack@eecs.umich.edu 1056384Sgblack@eecs.umich.edu dependGraph[i].next = NULL; 1068588Sgblack@eecs.umich.edu } 1078588Sgblack@eecs.umich.edu} 1086384Sgblack@eecs.umich.edu 1092101SN/Atemplate <class DynInstPtr> 1102101SN/Avoid 1112495SN/ADependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst) 1122495SN/A{ 1132495SN/A //Add this new, dependent instruction at the head of the dependency 1142495SN/A //chain. 1152495SN/A 1166384Sgblack@eecs.umich.edu // First create the entry that will be added to the head of the 1176384Sgblack@eecs.umich.edu // dependency chain. 1186384Sgblack@eecs.umich.edu DepEntry *new_entry = new DepEntry; 1196384Sgblack@eecs.umich.edu new_entry->next = dependGraph[idx].next; 1206384Sgblack@eecs.umich.edu new_entry->inst = new_inst; 1212495SN/A 1226384Sgblack@eecs.umich.edu // Then actually add it to the chain. 1232495SN/A dependGraph[idx].next = new_entry; 1242495SN/A 1252043SN/A ++memAllocCounter; 1262043SN/A} 1272025SN/A 1282043SN/A 1292686Sksewell@umich.edutemplate <class DynInstPtr> 1302686Sksewell@umich.eduvoid 1312123SN/ADependencyGraph<DynInstPtr>::remove(PhysRegIndex idx, 1322101SN/A DynInstPtr &inst_to_remove) 1336376Sgblack@eecs.umich.edu{ 1346376Sgblack@eecs.umich.edu DepEntry *prev = &dependGraph[idx]; 1356376Sgblack@eecs.umich.edu DepEntry *curr = dependGraph[idx].next; 1367792Sgblack@eecs.umich.edu 1376376Sgblack@eecs.umich.edu // Make sure curr isn't NULL. Because this instruction is being 1386376Sgblack@eecs.umich.edu // removed from a dependency list, it must have been placed there at 1396376Sgblack@eecs.umich.edu // an earlier time. The dependency chain should not be empty, 1406376Sgblack@eecs.umich.edu // unless the instruction dependent upon it is already ready. 1416376Sgblack@eecs.umich.edu if (curr == NULL) { 1426376Sgblack@eecs.umich.edu return; 1436376Sgblack@eecs.umich.edu } 1447792Sgblack@eecs.umich.edu 1456376Sgblack@eecs.umich.edu nodesRemoved++; 1466376Sgblack@eecs.umich.edu 1476376Sgblack@eecs.umich.edu // Find the instruction to remove within the dependency linked list. 1486376Sgblack@eecs.umich.edu while (curr->inst != inst_to_remove) { 1492101SN/A prev = curr; 1502042SN/A curr = curr->next; 1512101SN/A nodesTraversed++; 1527720Sgblack@eecs.umich.edu 1537792Sgblack@eecs.umich.edu assert(curr != NULL); 1547792Sgblack@eecs.umich.edu } 1557720Sgblack@eecs.umich.edu 1567720Sgblack@eecs.umich.edu // Now remove this instruction from the list. 1577792Sgblack@eecs.umich.edu prev->next = curr->next; 1587792Sgblack@eecs.umich.edu 1597720Sgblack@eecs.umich.edu --memAllocCounter; 1602101SN/A 1612101SN/A // Could push this off to the destructor of DependencyEntry 1622042SN/A curr->inst = NULL; 1632101SN/A 1642686Sksewell@umich.edu delete curr; 1652686Sksewell@umich.edu} 1668901Sandreas.hansson@arm.com 1678564Sgblack@eecs.umich.edutemplate <class DynInstPtr> 1688564Sgblack@eecs.umich.eduDynInstPtr 16910474Sandreas.hansson@arm.comDependencyGraph<DynInstPtr>::pop(PhysRegIndex idx) 1708564Sgblack@eecs.umich.edu{ 1712686Sksewell@umich.edu DepEntry *node; 17210474Sandreas.hansson@arm.com node = dependGraph[idx].next; 1732101SN/A DynInstPtr inst = NULL; 1742083SN/A if (node) { 1752043SN/A inst = node->inst; 1762025SN/A dependGraph[idx].next = node->next; 1772043SN/A node->inst = NULL; 1786384Sgblack@eecs.umich.edu memAllocCounter--; 1796384Sgblack@eecs.umich.edu delete node; 1804661Sksewell@umich.edu } 1816384Sgblack@eecs.umich.edu return inst; 1826384Sgblack@eecs.umich.edu} 1834661Sksewell@umich.edu 1842083SN/Atemplate <class DynInstPtr> 1852025SN/Avoid 1862043SN/ADependencyGraph<DynInstPtr>::dump() 1874661Sksewell@umich.edu{ 1888588Sgblack@eecs.umich.edu DepEntry *curr; 1898588Sgblack@eecs.umich.edu 1904661Sksewell@umich.edu for (int i = 0; i < numEntries; ++i) 1914661Sksewell@umich.edu { 1922686Sksewell@umich.edu curr = &dependGraph[i]; 1936384Sgblack@eecs.umich.edu 1948588Sgblack@eecs.umich.edu if (curr->inst) { 1958588Sgblack@eecs.umich.edu cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ", 1968588Sgblack@eecs.umich.edu i, curr->inst->readPC(), curr->inst->seqNum); 1976384Sgblack@eecs.umich.edu } else { 1985222Sksewell@umich.edu cprintf("dependGraph[%i]: No producer. consumer: ", i); 1995222Sksewell@umich.edu } 2006384Sgblack@eecs.umich.edu 2018588Sgblack@eecs.umich.edu while (curr->next != NULL) { 2028588Sgblack@eecs.umich.edu curr = curr->next; 2038588Sgblack@eecs.umich.edu 2046384Sgblack@eecs.umich.edu cprintf("%#x [sn:%lli] ", 2055222Sksewell@umich.edu curr->inst->readPC(), curr->inst->seqNum); 2062101SN/A } 2072084SN/A 2082025SN/A cprintf("\n"); 2092495SN/A } 2102495SN/A cprintf("memAllocCounter: %i\n", memAllocCounter); 2112495SN/A} 2126384Sgblack@eecs.umich.edu 2138564Sgblack@eecs.umich.edu#endif // __CPU_O3_DEP_GRAPH_HH__ 2148564Sgblack@eecs.umich.edu