dep_graph.hh revision 13472
12689Sktlim@umich.edu/* 29444SAndreas.Sandberg@ARM.com * Copyright (c) 2012 ARM Limited 39444SAndreas.Sandberg@ARM.com * All rights reserved 49444SAndreas.Sandberg@ARM.com * 59444SAndreas.Sandberg@ARM.com * The license below extends only to copyright in the software and shall 69444SAndreas.Sandberg@ARM.com * not be construed as granting a license to any other intellectual 79444SAndreas.Sandberg@ARM.com * property including but not limited to intellectual property relating 89444SAndreas.Sandberg@ARM.com * to a hardware implementation of the functionality of the software 99444SAndreas.Sandberg@ARM.com * licensed hereunder. You may use the software subject to the license 109444SAndreas.Sandberg@ARM.com * terms below provided that you ensure that this notice is replicated 119444SAndreas.Sandberg@ARM.com * unmodified and in its entirety in all distributions of the software, 129444SAndreas.Sandberg@ARM.com * modified or unmodified, in source code or in binary form. 139444SAndreas.Sandberg@ARM.com * 142689Sktlim@umich.edu * Copyright (c) 2006 The Regents of The University of Michigan 152689Sktlim@umich.edu * All rights reserved. 162689Sktlim@umich.edu * 172689Sktlim@umich.edu * Redistribution and use in source and binary forms, with or without 182689Sktlim@umich.edu * modification, are permitted provided that the following conditions are 192689Sktlim@umich.edu * met: redistributions of source code must retain the above copyright 202689Sktlim@umich.edu * notice, this list of conditions and the following disclaimer; 212689Sktlim@umich.edu * redistributions in binary form must reproduce the above copyright 222689Sktlim@umich.edu * notice, this list of conditions and the following disclaimer in the 232689Sktlim@umich.edu * documentation and/or other materials provided with the distribution; 242689Sktlim@umich.edu * neither the name of the copyright holders nor the names of its 252689Sktlim@umich.edu * contributors may be used to endorse or promote products derived from 262689Sktlim@umich.edu * this software without specific prior written permission. 272689Sktlim@umich.edu * 282689Sktlim@umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292689Sktlim@umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302689Sktlim@umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312689Sktlim@umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 322689Sktlim@umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 332689Sktlim@umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342689Sktlim@umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352689Sktlim@umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362689Sktlim@umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372689Sktlim@umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382689Sktlim@umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392689Sktlim@umich.edu * 402689Sktlim@umich.edu * Authors: Kevin Lim 412689Sktlim@umich.edu */ 422326SN/A 432326SN/A#ifndef __CPU_O3_DEP_GRAPH_HH__ 442326SN/A#define __CPU_O3_DEP_GRAPH_HH__ 452326SN/A 462326SN/A#include "cpu/o3/comm.hh" 472326SN/A 482348SN/A/** Node in a linked list. */ 492326SN/Atemplate <class DynInstPtr> 502326SN/Aclass DependencyEntry 512326SN/A{ 522326SN/A public: 532326SN/A DependencyEntry() 542326SN/A : inst(NULL), next(NULL) 552326SN/A { } 562326SN/A 572326SN/A DynInstPtr inst; 582326SN/A //Might want to include data about what arch. register the 592326SN/A //dependence is waiting on. 602326SN/A DependencyEntry<DynInstPtr> *next; 612326SN/A}; 622326SN/A 632348SN/A/** Array of linked list that maintains the dependencies between 642348SN/A * producing instructions and consuming instructions. Each linked 652348SN/A * list represents a single physical register, having the future 662348SN/A * producer of the register's value, and all consumers waiting on that 672348SN/A * value on the list. The head node of each linked list represents 682348SN/A * the producing instruction of that register. Instructions are put 692348SN/A * on the list upon reaching the IQ, and are removed from the list 702348SN/A * either when the producer completes, or the instruction is squashed. 712348SN/A*/ 722326SN/Atemplate <class DynInstPtr> 732326SN/Aclass DependencyGraph 742326SN/A{ 752326SN/A public: 762326SN/A typedef DependencyEntry<DynInstPtr> DepEntry; 772326SN/A 782348SN/A /** Default construction. Must call resize() prior to use. */ 792326SN/A DependencyGraph() 802326SN/A : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0) 812326SN/A { } 822326SN/A 832734Sktlim@umich.edu ~DependencyGraph(); 842734Sktlim@umich.edu 852348SN/A /** Resize the dependency graph to have num_entries registers. */ 862326SN/A void resize(int num_entries); 872326SN/A 882348SN/A /** Clears all of the linked lists. */ 892326SN/A void reset(); 902326SN/A 912348SN/A /** Inserts an instruction to be dependent on the given index. */ 9213429Srekai.gonzalezalberquilla@arm.com void insert(PhysRegIndex idx, const DynInstPtr &new_inst); 932326SN/A 942348SN/A /** Sets the producing instruction of a given register. */ 9513429Srekai.gonzalezalberquilla@arm.com void setInst(PhysRegIndex idx, const DynInstPtr &new_inst) 962326SN/A { dependGraph[idx].inst = new_inst; } 972326SN/A 982348SN/A /** Clears the producing instruction. */ 992326SN/A void clearInst(PhysRegIndex idx) 1002326SN/A { dependGraph[idx].inst = NULL; } 1012326SN/A 1022348SN/A /** Removes an instruction from a single linked list. */ 10313429Srekai.gonzalezalberquilla@arm.com void remove(PhysRegIndex idx, const DynInstPtr &inst_to_remove); 1042326SN/A 1052348SN/A /** Removes and returns the newest dependent of a specific register. */ 1062326SN/A DynInstPtr pop(PhysRegIndex idx); 1072326SN/A 1089444SAndreas.Sandberg@ARM.com /** Checks if the entire dependency graph is empty. */ 1099444SAndreas.Sandberg@ARM.com bool empty() const; 1109444SAndreas.Sandberg@ARM.com 1112348SN/A /** Checks if there are any dependents on a specific register. */ 1129444SAndreas.Sandberg@ARM.com bool empty(PhysRegIndex idx) const { return !dependGraph[idx].next; } 1132326SN/A 1142326SN/A /** Debugging function to dump out the dependency graph. 1152326SN/A */ 1162326SN/A void dump(); 1172326SN/A 1182326SN/A private: 1192326SN/A /** Array of linked lists. Each linked list is a list of all the 1202326SN/A * instructions that depend upon a given register. The actual 1212326SN/A * register's index is used to index into the graph; ie all 1222326SN/A * instructions in flight that are dependent upon r34 will be 1232326SN/A * in the linked list of dependGraph[34]. 1242326SN/A */ 12513472Srekai.gonzalezalberquilla@arm.com std::vector<DepEntry> dependGraph; 1262326SN/A 1272348SN/A /** Number of linked lists; identical to the number of registers. */ 1282326SN/A int numEntries; 1292326SN/A 1302326SN/A // Debug variable, remove when done testing. 1312326SN/A unsigned memAllocCounter; 1322326SN/A 1332326SN/A public: 1342348SN/A // Debug variable, remove when done testing. 1352326SN/A uint64_t nodesTraversed; 1362348SN/A // Debug variable, remove when done testing. 1372326SN/A uint64_t nodesRemoved; 1382326SN/A}; 1392326SN/A 1402326SN/Atemplate <class DynInstPtr> 1412734Sktlim@umich.eduDependencyGraph<DynInstPtr>::~DependencyGraph() 1422734Sktlim@umich.edu{ 1432734Sktlim@umich.edu} 1442734Sktlim@umich.edu 1452734Sktlim@umich.edutemplate <class DynInstPtr> 1462326SN/Avoid 1472326SN/ADependencyGraph<DynInstPtr>::resize(int num_entries) 1482326SN/A{ 1492326SN/A numEntries = num_entries; 15013472Srekai.gonzalezalberquilla@arm.com dependGraph.resize(numEntries); 1512326SN/A} 1522326SN/A 1532326SN/Atemplate <class DynInstPtr> 1542326SN/Avoid 1552326SN/ADependencyGraph<DynInstPtr>::reset() 1562326SN/A{ 1572326SN/A // Clear the dependency graph 1582326SN/A DepEntry *curr; 1592326SN/A DepEntry *prev; 1602326SN/A 1612326SN/A for (int i = 0; i < numEntries; ++i) { 1622326SN/A curr = dependGraph[i].next; 1632326SN/A 1642326SN/A while (curr) { 1652326SN/A memAllocCounter--; 1662326SN/A 1672326SN/A prev = curr; 1682326SN/A curr = prev->next; 1692326SN/A prev->inst = NULL; 1702326SN/A 1712326SN/A delete prev; 1722326SN/A } 1732326SN/A 1742326SN/A if (dependGraph[i].inst) { 1752326SN/A dependGraph[i].inst = NULL; 1762326SN/A } 1772326SN/A 1782326SN/A dependGraph[i].next = NULL; 1792326SN/A } 1802326SN/A} 1812326SN/A 1822326SN/Atemplate <class DynInstPtr> 1832326SN/Avoid 18413429Srekai.gonzalezalberquilla@arm.comDependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, 18513429Srekai.gonzalezalberquilla@arm.com const DynInstPtr &new_inst) 1862326SN/A{ 1872326SN/A //Add this new, dependent instruction at the head of the dependency 1882326SN/A //chain. 1892326SN/A 1902326SN/A // First create the entry that will be added to the head of the 1912326SN/A // dependency chain. 1922326SN/A DepEntry *new_entry = new DepEntry; 1932326SN/A new_entry->next = dependGraph[idx].next; 1942326SN/A new_entry->inst = new_inst; 1952326SN/A 1962326SN/A // Then actually add it to the chain. 1972326SN/A dependGraph[idx].next = new_entry; 1982326SN/A 1992326SN/A ++memAllocCounter; 2002326SN/A} 2012326SN/A 2022326SN/A 2032326SN/Atemplate <class DynInstPtr> 2042326SN/Avoid 2052326SN/ADependencyGraph<DynInstPtr>::remove(PhysRegIndex idx, 20613429Srekai.gonzalezalberquilla@arm.com const DynInstPtr &inst_to_remove) 2072326SN/A{ 2082326SN/A DepEntry *prev = &dependGraph[idx]; 2092326SN/A DepEntry *curr = dependGraph[idx].next; 2102326SN/A 2112326SN/A // Make sure curr isn't NULL. Because this instruction is being 2122326SN/A // removed from a dependency list, it must have been placed there at 2132326SN/A // an earlier time. The dependency chain should not be empty, 2142326SN/A // unless the instruction dependent upon it is already ready. 2152326SN/A if (curr == NULL) { 2162326SN/A return; 2172326SN/A } 2182326SN/A 2192326SN/A nodesRemoved++; 2202326SN/A 2212326SN/A // Find the instruction to remove within the dependency linked list. 2222326SN/A while (curr->inst != inst_to_remove) { 2232326SN/A prev = curr; 2242326SN/A curr = curr->next; 2252326SN/A nodesTraversed++; 2262326SN/A 2272326SN/A assert(curr != NULL); 2282326SN/A } 2292326SN/A 2302326SN/A // Now remove this instruction from the list. 2312326SN/A prev->next = curr->next; 2322326SN/A 2332326SN/A --memAllocCounter; 2342326SN/A 2352326SN/A // Could push this off to the destructor of DependencyEntry 2362326SN/A curr->inst = NULL; 2372326SN/A 2382326SN/A delete curr; 2392326SN/A} 2402326SN/A 2412326SN/Atemplate <class DynInstPtr> 2422326SN/ADynInstPtr 2432326SN/ADependencyGraph<DynInstPtr>::pop(PhysRegIndex idx) 2442326SN/A{ 2452326SN/A DepEntry *node; 2462326SN/A node = dependGraph[idx].next; 2472326SN/A DynInstPtr inst = NULL; 2482326SN/A if (node) { 2492326SN/A inst = node->inst; 2502326SN/A dependGraph[idx].next = node->next; 2512326SN/A node->inst = NULL; 2522326SN/A memAllocCounter--; 2532326SN/A delete node; 2542326SN/A } 2552326SN/A return inst; 2562326SN/A} 2572326SN/A 2582326SN/Atemplate <class DynInstPtr> 2599444SAndreas.Sandberg@ARM.combool 2609444SAndreas.Sandberg@ARM.comDependencyGraph<DynInstPtr>::empty() const 2619444SAndreas.Sandberg@ARM.com{ 2629444SAndreas.Sandberg@ARM.com for (int i = 0; i < numEntries; ++i) { 2639444SAndreas.Sandberg@ARM.com if (!empty(i)) 2649444SAndreas.Sandberg@ARM.com return false; 2659444SAndreas.Sandberg@ARM.com } 2669444SAndreas.Sandberg@ARM.com return true; 2679444SAndreas.Sandberg@ARM.com} 2689444SAndreas.Sandberg@ARM.com 2699444SAndreas.Sandberg@ARM.comtemplate <class DynInstPtr> 2702326SN/Avoid 2712326SN/ADependencyGraph<DynInstPtr>::dump() 2722326SN/A{ 2732326SN/A DepEntry *curr; 2742326SN/A 2752326SN/A for (int i = 0; i < numEntries; ++i) 2762326SN/A { 2772326SN/A curr = &dependGraph[i]; 2782326SN/A 2792326SN/A if (curr->inst) { 2807720Sgblack@eecs.umich.edu cprintf("dependGraph[%i]: producer: %s [sn:%lli] consumer: ", 2817720Sgblack@eecs.umich.edu i, curr->inst->pcState(), curr->inst->seqNum); 2822326SN/A } else { 2832326SN/A cprintf("dependGraph[%i]: No producer. consumer: ", i); 2842326SN/A } 2852326SN/A 2862326SN/A while (curr->next != NULL) { 2872326SN/A curr = curr->next; 2882326SN/A 2897720Sgblack@eecs.umich.edu cprintf("%s [sn:%lli] ", 2907720Sgblack@eecs.umich.edu curr->inst->pcState(), curr->inst->seqNum); 2912326SN/A } 2922326SN/A 2932326SN/A cprintf("\n"); 2942326SN/A } 2952326SN/A cprintf("memAllocCounter: %i\n", memAllocCounter); 2962326SN/A} 2972326SN/A 2982326SN/A#endif // __CPU_O3_DEP_GRAPH_HH__ 299