dep_graph.hh revision 7720
11689SN/A/* 27598Sminkyu.jeong@arm.com * Copyright (c) 2006 The Regents of The University of Michigan 37598Sminkyu.jeong@arm.com * All rights reserved. 47598Sminkyu.jeong@arm.com * 57598Sminkyu.jeong@arm.com * Redistribution and use in source and binary forms, with or without 67598Sminkyu.jeong@arm.com * modification, are permitted provided that the following conditions are 77598Sminkyu.jeong@arm.com * met: redistributions of source code must retain the above copyright 87598Sminkyu.jeong@arm.com * notice, this list of conditions and the following disclaimer; 97598Sminkyu.jeong@arm.com * redistributions in binary form must reproduce the above copyright 107598Sminkyu.jeong@arm.com * notice, this list of conditions and the following disclaimer in the 117598Sminkyu.jeong@arm.com * documentation and/or other materials provided with the distribution; 127598Sminkyu.jeong@arm.com * neither the name of the copyright holders nor the names of its 137598Sminkyu.jeong@arm.com * contributors may be used to endorse or promote products derived from 142326SN/A * this software without specific prior written permission. 151689SN/A * 161689SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 171689SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 181689SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 191689SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 201689SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 211689SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 221689SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 231689SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 241689SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 251689SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 261689SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 271689SN/A * 281689SN/A * Authors: Kevin Lim 291689SN/A */ 301689SN/A 311689SN/A#ifndef __CPU_O3_DEP_GRAPH_HH__ 321689SN/A#define __CPU_O3_DEP_GRAPH_HH__ 331689SN/A 341689SN/A#include "cpu/o3/comm.hh" 351689SN/A 361689SN/A/** Node in a linked list. */ 371689SN/Atemplate <class DynInstPtr> 381689SN/Aclass DependencyEntry 392665Ssaidi@eecs.umich.edu{ 402665Ssaidi@eecs.umich.edu public: 411689SN/A DependencyEntry() 421689SN/A : inst(NULL), next(NULL) 431060SN/A { } 441060SN/A 451689SN/A DynInstPtr inst; 461060SN/A //Might want to include data about what arch. register the 471060SN/A //dependence is waiting on. 481060SN/A DependencyEntry<DynInstPtr> *next; 497813Ssteve.reinhardt@amd.com}; 506658Snate@binkert.org 512292SN/A/** Array of linked list that maintains the dependencies between 521717SN/A * producing instructions and consuming instructions. Each linked 535529Snate@binkert.org * list represents a single physical register, having the future 541060SN/A * producer of the register's value, and all consumers waiting on that 556221Snate@binkert.org * value on the list. The head node of each linked list represents 566221Snate@binkert.org * the producing instruction of that register. Instructions are put 571681SN/A * on the list upon reaching the IQ, and are removed from the list 585529Snate@binkert.org * either when the producer completes, or the instruction is squashed. 592873Sktlim@umich.edu*/ 604329Sktlim@umich.edutemplate <class DynInstPtr> 614329Sktlim@umich.educlass DependencyGraph 624329Sktlim@umich.edu{ 632292SN/A public: 642292SN/A typedef DependencyEntry<DynInstPtr> DepEntry; 652292SN/A 662292SN/A /** Default construction. Must call resize() prior to use. */ 672820Sktlim@umich.edu DependencyGraph() 682292SN/A : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0) 692820Sktlim@umich.edu { } 702820Sktlim@umich.edu 715529Snate@binkert.org ~DependencyGraph(); 722307SN/A 731060SN/A /** Resize the dependency graph to have num_entries registers. */ 742292SN/A void resize(int num_entries); 752292SN/A 762292SN/A /** Clears all of the linked lists. */ 771060SN/A void reset(); 781060SN/A 791060SN/A /** Inserts an instruction to be dependent on the given index. */ 801060SN/A void insert(PhysRegIndex idx, DynInstPtr &new_inst); 811060SN/A 821060SN/A /** Sets the producing instruction of a given register. */ 831681SN/A void setInst(PhysRegIndex idx, DynInstPtr &new_inst) 846221Snate@binkert.org { dependGraph[idx].inst = new_inst; } 856221Snate@binkert.org 866221Snate@binkert.org /** Clears the producing instruction. */ 876221Snate@binkert.org void clearInst(PhysRegIndex idx) 882292SN/A { dependGraph[idx].inst = NULL; } 892292SN/A 902820Sktlim@umich.edu /** Removes an instruction from a single linked list. */ 912820Sktlim@umich.edu void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove); 922292SN/A 932292SN/A /** Removes and returns the newest dependent of a specific register. */ 942820Sktlim@umich.edu DynInstPtr pop(PhysRegIndex idx); 952820Sktlim@umich.edu 962292SN/A /** Checks if there are any dependents on a specific register. */ 972292SN/A bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; } 982292SN/A 992292SN/A /** Debugging function to dump out the dependency graph. 1002292SN/A */ 1012292SN/A void dump(); 1022292SN/A 1032292SN/A private: 1041060SN/A /** Array of linked lists. Each linked list is a list of all the 1051060SN/A * instructions that depend upon a given register. The actual 1061681SN/A * register's index is used to index into the graph; ie all 1071062SN/A * instructions in flight that are dependent upon r34 will be 1082292SN/A * in the linked list of dependGraph[34]. 1091062SN/A */ 1102301SN/A DepEntry *dependGraph; 1112301SN/A 1121062SN/A /** Number of linked lists; identical to the number of registers. */ 1132727Sktlim@umich.edu int numEntries; 1141062SN/A 1151062SN/A // Debug variable, remove when done testing. 1161062SN/A unsigned memAllocCounter; 1171062SN/A 1181062SN/A public: 1191062SN/A // Debug variable, remove when done testing. 1201062SN/A uint64_t nodesTraversed; 1211062SN/A // Debug variable, remove when done testing. 1221062SN/A uint64_t nodesRemoved; 1231062SN/A}; 1241062SN/A 1251062SN/Atemplate <class DynInstPtr> 1261062SN/ADependencyGraph<DynInstPtr>::~DependencyGraph() 1271062SN/A{ 1281062SN/A delete [] dependGraph; 1291062SN/A} 1301062SN/A 1311062SN/Atemplate <class DynInstPtr> 1321062SN/Avoid 1331062SN/ADependencyGraph<DynInstPtr>::resize(int num_entries) 1341062SN/A{ 1351062SN/A numEntries = num_entries; 1361062SN/A dependGraph = new DepEntry[numEntries]; 1371062SN/A} 1381062SN/A 1391062SN/Atemplate <class DynInstPtr> 1401062SN/Avoid 1411062SN/ADependencyGraph<DynInstPtr>::reset() 1421062SN/A{ 1431062SN/A // Clear the dependency graph 1441062SN/A DepEntry *curr; 1451062SN/A DepEntry *prev; 1461062SN/A 1471062SN/A for (int i = 0; i < numEntries; ++i) { 1481062SN/A curr = dependGraph[i].next; 1491062SN/A 1501062SN/A while (curr) { 1511062SN/A memAllocCounter--; 1521062SN/A 1531062SN/A prev = curr; 1541062SN/A curr = prev->next; 1552292SN/A prev->inst = NULL; 1562292SN/A 1572292SN/A delete prev; 1582292SN/A } 1591062SN/A 1601062SN/A if (dependGraph[i].inst) { 1611062SN/A dependGraph[i].inst = NULL; 1621062SN/A } 1631062SN/A 1641062SN/A dependGraph[i].next = NULL; 1651062SN/A } 1662292SN/A} 1672292SN/A 1682292SN/Atemplate <class DynInstPtr> 1692292SN/Avoid 1702292SN/ADependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst) 1712292SN/A{ 1722292SN/A //Add this new, dependent instruction at the head of the dependency 1732292SN/A //chain. 1742292SN/A 1752292SN/A // First create the entry that will be added to the head of the 1762301SN/A // dependency chain. 1772727Sktlim@umich.edu DepEntry *new_entry = new DepEntry; 1782353SN/A new_entry->next = dependGraph[idx].next; 1792727Sktlim@umich.edu new_entry->inst = new_inst; 1802727Sktlim@umich.edu 1812727Sktlim@umich.edu // Then actually add it to the chain. 1826221Snate@binkert.org dependGraph[idx].next = new_entry; 1832353SN/A 1842727Sktlim@umich.edu ++memAllocCounter; 1852727Sktlim@umich.edu} 1862727Sktlim@umich.edu 1872727Sktlim@umich.edu 1882353SN/Atemplate <class DynInstPtr> 1892727Sktlim@umich.eduvoid 1902727Sktlim@umich.eduDependencyGraph<DynInstPtr>::remove(PhysRegIndex idx, 1912727Sktlim@umich.edu DynInstPtr &inst_to_remove) 1926221Snate@binkert.org{ 1932301SN/A DepEntry *prev = &dependGraph[idx]; 1942301SN/A DepEntry *curr = dependGraph[idx].next; 1952727Sktlim@umich.edu 1962301SN/A // Make sure curr isn't NULL. Because this instruction is being 1972727Sktlim@umich.edu // removed from a dependency list, it must have been placed there at 1986221Snate@binkert.org // an earlier time. The dependency chain should not be empty, 1992301SN/A // unless the instruction dependent upon it is already ready. 2002301SN/A if (curr == NULL) { 2012727Sktlim@umich.edu return; 2022301SN/A } 2032727Sktlim@umich.edu 2046221Snate@binkert.org nodesRemoved++; 2052301SN/A 2062301SN/A // Find the instruction to remove within the dependency linked list. 2072727Sktlim@umich.edu while (curr->inst != inst_to_remove) { 2082301SN/A prev = curr; 2092727Sktlim@umich.edu curr = curr->next; 2106221Snate@binkert.org nodesTraversed++; 2112301SN/A 2122301SN/A assert(curr != NULL); 2132727Sktlim@umich.edu } 2142301SN/A 2152301SN/A // Now remove this instruction from the list. 2162301SN/A prev->next = curr->next; 2172301SN/A 2182727Sktlim@umich.edu --memAllocCounter; 2192727Sktlim@umich.edu 2202727Sktlim@umich.edu // Could push this off to the destructor of DependencyEntry 2212727Sktlim@umich.edu curr->inst = NULL; 2222727Sktlim@umich.edu 2232727Sktlim@umich.edu delete curr; 2242727Sktlim@umich.edu} 2252727Sktlim@umich.edu 2262727Sktlim@umich.edutemplate <class DynInstPtr> 2272301SN/ADynInstPtr 2282301SN/ADependencyGraph<DynInstPtr>::pop(PhysRegIndex idx) 2296221Snate@binkert.org{ 2302301SN/A DepEntry *node; 2312301SN/A node = dependGraph[idx].next; 2322727Sktlim@umich.edu DynInstPtr inst = NULL; 2332301SN/A if (node) { 2342326SN/A inst = node->inst; 2356221Snate@binkert.org dependGraph[idx].next = node->next; 2362301SN/A node->inst = NULL; 2372301SN/A memAllocCounter--; 2382727Sktlim@umich.edu delete node; 2392301SN/A } 2402326SN/A return inst; 2416221Snate@binkert.org} 2422301SN/A 2432301SN/Atemplate <class DynInstPtr> 2442727Sktlim@umich.eduvoid 2452301SN/ADependencyGraph<DynInstPtr>::dump() 2462326SN/A{ 2476221Snate@binkert.org DepEntry *curr; 2482301SN/A 2492301SN/A for (int i = 0; i < numEntries; ++i) 2502727Sktlim@umich.edu { 2512301SN/A curr = &dependGraph[i]; 2522326SN/A 2536221Snate@binkert.org if (curr->inst) { 2542301SN/A cprintf("dependGraph[%i]: producer: %s [sn:%lli] consumer: ", 2552301SN/A i, curr->inst->pcState(), curr->inst->seqNum); 2562727Sktlim@umich.edu } else { 2572301SN/A cprintf("dependGraph[%i]: No producer. consumer: ", i); 2582326SN/A } 2592301SN/A 2602301SN/A while (curr->next != NULL) { 2612727Sktlim@umich.edu curr = curr->next; 2622301SN/A 2632326SN/A cprintf("%s [sn:%lli] ", 2642301SN/A curr->inst->pcState(), curr->inst->seqNum); 2652326SN/A } 2662301SN/A 2672301SN/A cprintf("\n"); 2682727Sktlim@umich.edu } 2692301SN/A cprintf("memAllocCounter: %i\n", memAllocCounter); 2702326SN/A} 2712301SN/A 2722326SN/A#endif // __CPU_O3_DEP_GRAPH_HH__ 2732301SN/A