dep_graph.hh revision 2689
12689Sktlim@umich.edu/* 22689Sktlim@umich.edu * Copyright (c) 2006 The Regents of The University of Michigan 32689Sktlim@umich.edu * All rights reserved. 42689Sktlim@umich.edu * 52689Sktlim@umich.edu * Redistribution and use in source and binary forms, with or without 62689Sktlim@umich.edu * modification, are permitted provided that the following conditions are 72689Sktlim@umich.edu * met: redistributions of source code must retain the above copyright 82689Sktlim@umich.edu * notice, this list of conditions and the following disclaimer; 92689Sktlim@umich.edu * redistributions in binary form must reproduce the above copyright 102689Sktlim@umich.edu * notice, this list of conditions and the following disclaimer in the 112689Sktlim@umich.edu * documentation and/or other materials provided with the distribution; 122689Sktlim@umich.edu * neither the name of the copyright holders nor the names of its 132689Sktlim@umich.edu * contributors may be used to endorse or promote products derived from 142689Sktlim@umich.edu * this software without specific prior written permission. 152689Sktlim@umich.edu * 162689Sktlim@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 172689Sktlim@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 182689Sktlim@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 192689Sktlim@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 202689Sktlim@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 212689Sktlim@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 222689Sktlim@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 232689Sktlim@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 242689Sktlim@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 252689Sktlim@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 262689Sktlim@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 272689Sktlim@umich.edu * 282689Sktlim@umich.edu * Authors: Kevin Lim 292689Sktlim@umich.edu */ 302326SN/A 312326SN/A#ifndef __CPU_O3_DEP_GRAPH_HH__ 322326SN/A#define __CPU_O3_DEP_GRAPH_HH__ 332326SN/A 342326SN/A#include "cpu/o3/comm.hh" 352326SN/A 362348SN/A/** Node in a linked list. */ 372326SN/Atemplate <class DynInstPtr> 382326SN/Aclass DependencyEntry 392326SN/A{ 402326SN/A public: 412326SN/A DependencyEntry() 422326SN/A : inst(NULL), next(NULL) 432326SN/A { } 442326SN/A 452326SN/A DynInstPtr inst; 462326SN/A //Might want to include data about what arch. register the 472326SN/A //dependence is waiting on. 482326SN/A DependencyEntry<DynInstPtr> *next; 492326SN/A}; 502326SN/A 512348SN/A/** Array of linked list that maintains the dependencies between 522348SN/A * producing instructions and consuming instructions. Each linked 532348SN/A * list represents a single physical register, having the future 542348SN/A * producer of the register's value, and all consumers waiting on that 552348SN/A * value on the list. The head node of each linked list represents 562348SN/A * the producing instruction of that register. Instructions are put 572348SN/A * on the list upon reaching the IQ, and are removed from the list 582348SN/A * either when the producer completes, or the instruction is squashed. 592348SN/A*/ 602326SN/Atemplate <class DynInstPtr> 612326SN/Aclass DependencyGraph 622326SN/A{ 632326SN/A public: 642326SN/A typedef DependencyEntry<DynInstPtr> DepEntry; 652326SN/A 662348SN/A /** Default construction. Must call resize() prior to use. */ 672326SN/A DependencyGraph() 682326SN/A : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0) 692326SN/A { } 702326SN/A 712348SN/A /** Resize the dependency graph to have num_entries registers. */ 722326SN/A void resize(int num_entries); 732326SN/A 742348SN/A /** Clears all of the linked lists. */ 752326SN/A void reset(); 762326SN/A 772348SN/A /** Inserts an instruction to be dependent on the given index. */ 782326SN/A void insert(PhysRegIndex idx, DynInstPtr &new_inst); 792326SN/A 802348SN/A /** Sets the producing instruction of a given register. */ 812326SN/A void setInst(PhysRegIndex idx, DynInstPtr &new_inst) 822326SN/A { dependGraph[idx].inst = new_inst; } 832326SN/A 842348SN/A /** Clears the producing instruction. */ 852326SN/A void clearInst(PhysRegIndex idx) 862326SN/A { dependGraph[idx].inst = NULL; } 872326SN/A 882348SN/A /** Removes an instruction from a single linked list. */ 892326SN/A void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove); 902326SN/A 912348SN/A /** Removes and returns the newest dependent of a specific register. */ 922326SN/A DynInstPtr pop(PhysRegIndex idx); 932326SN/A 942348SN/A /** Checks if there are any dependents on a specific register. */ 952326SN/A bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; } 962326SN/A 972326SN/A /** Debugging function to dump out the dependency graph. 982326SN/A */ 992326SN/A void dump(); 1002326SN/A 1012326SN/A private: 1022326SN/A /** Array of linked lists. Each linked list is a list of all the 1032326SN/A * instructions that depend upon a given register. The actual 1042326SN/A * register's index is used to index into the graph; ie all 1052326SN/A * instructions in flight that are dependent upon r34 will be 1062326SN/A * in the linked list of dependGraph[34]. 1072326SN/A */ 1082326SN/A DepEntry *dependGraph; 1092326SN/A 1102348SN/A /** Number of linked lists; identical to the number of registers. */ 1112326SN/A int numEntries; 1122326SN/A 1132326SN/A // Debug variable, remove when done testing. 1142326SN/A unsigned memAllocCounter; 1152326SN/A 1162326SN/A public: 1172348SN/A // Debug variable, remove when done testing. 1182326SN/A uint64_t nodesTraversed; 1192348SN/A // Debug variable, remove when done testing. 1202326SN/A uint64_t nodesRemoved; 1212326SN/A}; 1222326SN/A 1232326SN/Atemplate <class DynInstPtr> 1242326SN/Avoid 1252326SN/ADependencyGraph<DynInstPtr>::resize(int num_entries) 1262326SN/A{ 1272326SN/A numEntries = num_entries; 1282326SN/A dependGraph = new DepEntry[numEntries]; 1292326SN/A} 1302326SN/A 1312326SN/Atemplate <class DynInstPtr> 1322326SN/Avoid 1332326SN/ADependencyGraph<DynInstPtr>::reset() 1342326SN/A{ 1352326SN/A // Clear the dependency graph 1362326SN/A DepEntry *curr; 1372326SN/A DepEntry *prev; 1382326SN/A 1392326SN/A for (int i = 0; i < numEntries; ++i) { 1402326SN/A curr = dependGraph[i].next; 1412326SN/A 1422326SN/A while (curr) { 1432326SN/A memAllocCounter--; 1442326SN/A 1452326SN/A prev = curr; 1462326SN/A curr = prev->next; 1472326SN/A prev->inst = NULL; 1482326SN/A 1492326SN/A delete prev; 1502326SN/A } 1512326SN/A 1522326SN/A if (dependGraph[i].inst) { 1532326SN/A dependGraph[i].inst = NULL; 1542326SN/A } 1552326SN/A 1562326SN/A dependGraph[i].next = NULL; 1572326SN/A } 1582326SN/A} 1592326SN/A 1602326SN/Atemplate <class DynInstPtr> 1612326SN/Avoid 1622326SN/ADependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst) 1632326SN/A{ 1642326SN/A //Add this new, dependent instruction at the head of the dependency 1652326SN/A //chain. 1662326SN/A 1672326SN/A // First create the entry that will be added to the head of the 1682326SN/A // dependency chain. 1692326SN/A DepEntry *new_entry = new DepEntry; 1702326SN/A new_entry->next = dependGraph[idx].next; 1712326SN/A new_entry->inst = new_inst; 1722326SN/A 1732326SN/A // Then actually add it to the chain. 1742326SN/A dependGraph[idx].next = new_entry; 1752326SN/A 1762326SN/A ++memAllocCounter; 1772326SN/A} 1782326SN/A 1792326SN/A 1802326SN/Atemplate <class DynInstPtr> 1812326SN/Avoid 1822326SN/ADependencyGraph<DynInstPtr>::remove(PhysRegIndex idx, 1832326SN/A DynInstPtr &inst_to_remove) 1842326SN/A{ 1852326SN/A DepEntry *prev = &dependGraph[idx]; 1862326SN/A DepEntry *curr = dependGraph[idx].next; 1872326SN/A 1882326SN/A // Make sure curr isn't NULL. Because this instruction is being 1892326SN/A // removed from a dependency list, it must have been placed there at 1902326SN/A // an earlier time. The dependency chain should not be empty, 1912326SN/A // unless the instruction dependent upon it is already ready. 1922326SN/A if (curr == NULL) { 1932326SN/A return; 1942326SN/A } 1952326SN/A 1962326SN/A nodesRemoved++; 1972326SN/A 1982326SN/A // Find the instruction to remove within the dependency linked list. 1992326SN/A while (curr->inst != inst_to_remove) { 2002326SN/A prev = curr; 2012326SN/A curr = curr->next; 2022326SN/A nodesTraversed++; 2032326SN/A 2042326SN/A assert(curr != NULL); 2052326SN/A } 2062326SN/A 2072326SN/A // Now remove this instruction from the list. 2082326SN/A prev->next = curr->next; 2092326SN/A 2102326SN/A --memAllocCounter; 2112326SN/A 2122326SN/A // Could push this off to the destructor of DependencyEntry 2132326SN/A curr->inst = NULL; 2142326SN/A 2152326SN/A delete curr; 2162326SN/A} 2172326SN/A 2182326SN/Atemplate <class DynInstPtr> 2192326SN/ADynInstPtr 2202326SN/ADependencyGraph<DynInstPtr>::pop(PhysRegIndex idx) 2212326SN/A{ 2222326SN/A DepEntry *node; 2232326SN/A node = dependGraph[idx].next; 2242326SN/A DynInstPtr inst = NULL; 2252326SN/A if (node) { 2262326SN/A inst = node->inst; 2272326SN/A dependGraph[idx].next = node->next; 2282326SN/A node->inst = NULL; 2292326SN/A memAllocCounter--; 2302326SN/A delete node; 2312326SN/A } 2322326SN/A return inst; 2332326SN/A} 2342326SN/A 2352326SN/Atemplate <class DynInstPtr> 2362326SN/Avoid 2372326SN/ADependencyGraph<DynInstPtr>::dump() 2382326SN/A{ 2392326SN/A DepEntry *curr; 2402326SN/A 2412326SN/A for (int i = 0; i < numEntries; ++i) 2422326SN/A { 2432326SN/A curr = &dependGraph[i]; 2442326SN/A 2452326SN/A if (curr->inst) { 2462326SN/A cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ", 2472326SN/A i, curr->inst->readPC(), curr->inst->seqNum); 2482326SN/A } else { 2492326SN/A cprintf("dependGraph[%i]: No producer. consumer: ", i); 2502326SN/A } 2512326SN/A 2522326SN/A while (curr->next != NULL) { 2532326SN/A curr = curr->next; 2542326SN/A 2552326SN/A cprintf("%#x [sn:%lli] ", 2562326SN/A curr->inst->readPC(), curr->inst->seqNum); 2572326SN/A } 2582326SN/A 2592326SN/A cprintf("\n"); 2602326SN/A } 2612326SN/A cprintf("memAllocCounter: %i\n", memAllocCounter); 2622326SN/A} 2632326SN/A 2642326SN/A#endif // __CPU_O3_DEP_GRAPH_HH__ 265