| 1/* 2 * Copyright (c) 2006 The Regents of The University of Michigan 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer; 9 * redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution; 12 * neither the name of the copyright holders nor the names of its 13 * contributors may be used to endorse or promote products derived from 14 * this software without specific prior written permission. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 * 28 * Authors: Kevin Lim 29 */
|
1 2#ifndef __CPU_O3_DEP_GRAPH_HH__ 3#define __CPU_O3_DEP_GRAPH_HH__ 4 5#include "cpu/o3/comm.hh" 6 7/** Node in a linked list. */ 8template <class DynInstPtr> 9class DependencyEntry 10{ 11 public: 12 DependencyEntry() 13 : inst(NULL), next(NULL) 14 { } 15 16 DynInstPtr inst; 17 //Might want to include data about what arch. register the 18 //dependence is waiting on. 19 DependencyEntry<DynInstPtr> *next; 20}; 21 22/** Array of linked list that maintains the dependencies between 23 * producing instructions and consuming instructions. Each linked 24 * list represents a single physical register, having the future 25 * producer of the register's value, and all consumers waiting on that 26 * value on the list. The head node of each linked list represents 27 * the producing instruction of that register. Instructions are put 28 * on the list upon reaching the IQ, and are removed from the list 29 * either when the producer completes, or the instruction is squashed. 30*/ 31template <class DynInstPtr> 32class DependencyGraph 33{ 34 public: 35 typedef DependencyEntry<DynInstPtr> DepEntry; 36 37 /** Default construction. Must call resize() prior to use. */ 38 DependencyGraph() 39 : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0) 40 { } 41 42 /** Resize the dependency graph to have num_entries registers. */ 43 void resize(int num_entries); 44 45 /** Clears all of the linked lists. */ 46 void reset(); 47 48 /** Inserts an instruction to be dependent on the given index. */ 49 void insert(PhysRegIndex idx, DynInstPtr &new_inst); 50 51 /** Sets the producing instruction of a given register. */ 52 void setInst(PhysRegIndex idx, DynInstPtr &new_inst) 53 { dependGraph[idx].inst = new_inst; } 54 55 /** Clears the producing instruction. */ 56 void clearInst(PhysRegIndex idx) 57 { dependGraph[idx].inst = NULL; } 58 59 /** Removes an instruction from a single linked list. */ 60 void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove); 61 62 /** Removes and returns the newest dependent of a specific register. */ 63 DynInstPtr pop(PhysRegIndex idx); 64 65 /** Checks if there are any dependents on a specific register. */ 66 bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; } 67 68 /** Debugging function to dump out the dependency graph. 69 */ 70 void dump(); 71 72 private: 73 /** Array of linked lists. Each linked list is a list of all the 74 * instructions that depend upon a given register. The actual 75 * register's index is used to index into the graph; ie all 76 * instructions in flight that are dependent upon r34 will be 77 * in the linked list of dependGraph[34]. 78 */ 79 DepEntry *dependGraph; 80 81 /** Number of linked lists; identical to the number of registers. */ 82 int numEntries; 83 84 // Debug variable, remove when done testing. 85 unsigned memAllocCounter; 86 87 public: 88 // Debug variable, remove when done testing. 89 uint64_t nodesTraversed; 90 // Debug variable, remove when done testing. 91 uint64_t nodesRemoved; 92}; 93 94template <class DynInstPtr> 95void 96DependencyGraph<DynInstPtr>::resize(int num_entries) 97{ 98 numEntries = num_entries; 99 dependGraph = new DepEntry[numEntries]; 100} 101 102template <class DynInstPtr> 103void 104DependencyGraph<DynInstPtr>::reset() 105{ 106 // Clear the dependency graph 107 DepEntry *curr; 108 DepEntry *prev; 109 110 for (int i = 0; i < numEntries; ++i) { 111 curr = dependGraph[i].next; 112 113 while (curr) { 114 memAllocCounter--; 115 116 prev = curr; 117 curr = prev->next; 118 prev->inst = NULL; 119 120 delete prev; 121 } 122 123 if (dependGraph[i].inst) { 124 dependGraph[i].inst = NULL; 125 } 126 127 dependGraph[i].next = NULL; 128 } 129} 130 131template <class DynInstPtr> 132void 133DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst) 134{ 135 //Add this new, dependent instruction at the head of the dependency 136 //chain. 137 138 // First create the entry that will be added to the head of the 139 // dependency chain. 140 DepEntry *new_entry = new DepEntry; 141 new_entry->next = dependGraph[idx].next; 142 new_entry->inst = new_inst; 143 144 // Then actually add it to the chain. 145 dependGraph[idx].next = new_entry; 146 147 ++memAllocCounter; 148} 149 150 151template <class DynInstPtr> 152void 153DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx, 154 DynInstPtr &inst_to_remove) 155{ 156 DepEntry *prev = &dependGraph[idx]; 157 DepEntry *curr = dependGraph[idx].next; 158 159 // Make sure curr isn't NULL. Because this instruction is being 160 // removed from a dependency list, it must have been placed there at 161 // an earlier time. The dependency chain should not be empty, 162 // unless the instruction dependent upon it is already ready. 163 if (curr == NULL) { 164 return; 165 } 166 167 nodesRemoved++; 168 169 // Find the instruction to remove within the dependency linked list. 170 while (curr->inst != inst_to_remove) { 171 prev = curr; 172 curr = curr->next; 173 nodesTraversed++; 174 175 assert(curr != NULL); 176 } 177 178 // Now remove this instruction from the list. 179 prev->next = curr->next; 180 181 --memAllocCounter; 182 183 // Could push this off to the destructor of DependencyEntry 184 curr->inst = NULL; 185 186 delete curr; 187} 188 189template <class DynInstPtr> 190DynInstPtr 191DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx) 192{ 193 DepEntry *node; 194 node = dependGraph[idx].next; 195 DynInstPtr inst = NULL; 196 if (node) { 197 inst = node->inst; 198 dependGraph[idx].next = node->next; 199 node->inst = NULL; 200 memAllocCounter--; 201 delete node; 202 } 203 return inst; 204} 205 206template <class DynInstPtr> 207void 208DependencyGraph<DynInstPtr>::dump() 209{ 210 DepEntry *curr; 211 212 for (int i = 0; i < numEntries; ++i) 213 { 214 curr = &dependGraph[i]; 215 216 if (curr->inst) { 217 cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ", 218 i, curr->inst->readPC(), curr->inst->seqNum); 219 } else { 220 cprintf("dependGraph[%i]: No producer. consumer: ", i); 221 } 222 223 while (curr->next != NULL) { 224 curr = curr->next; 225 226 cprintf("%#x [sn:%lli] ", 227 curr->inst->readPC(), curr->inst->seqNum); 228 } 229 230 cprintf("\n"); 231 } 232 cprintf("memAllocCounter: %i\n", memAllocCounter); 233} 234 235#endif // __CPU_O3_DEP_GRAPH_HH__
| 30 31#ifndef __CPU_O3_DEP_GRAPH_HH__ 32#define __CPU_O3_DEP_GRAPH_HH__ 33 34#include "cpu/o3/comm.hh" 35 36/** Node in a linked list. */ 37template <class DynInstPtr> 38class DependencyEntry 39{ 40 public: 41 DependencyEntry() 42 : inst(NULL), next(NULL) 43 { } 44 45 DynInstPtr inst; 46 //Might want to include data about what arch. register the 47 //dependence is waiting on. 48 DependencyEntry<DynInstPtr> *next; 49}; 50 51/** Array of linked list that maintains the dependencies between 52 * producing instructions and consuming instructions. Each linked 53 * list represents a single physical register, having the future 54 * producer of the register's value, and all consumers waiting on that 55 * value on the list. The head node of each linked list represents 56 * the producing instruction of that register. Instructions are put 57 * on the list upon reaching the IQ, and are removed from the list 58 * either when the producer completes, or the instruction is squashed. 59*/ 60template <class DynInstPtr> 61class DependencyGraph 62{ 63 public: 64 typedef DependencyEntry<DynInstPtr> DepEntry; 65 66 /** Default construction. Must call resize() prior to use. */ 67 DependencyGraph() 68 : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0) 69 { } 70 71 /** Resize the dependency graph to have num_entries registers. */ 72 void resize(int num_entries); 73 74 /** Clears all of the linked lists. */ 75 void reset(); 76 77 /** Inserts an instruction to be dependent on the given index. */ 78 void insert(PhysRegIndex idx, DynInstPtr &new_inst); 79 80 /** Sets the producing instruction of a given register. */ 81 void setInst(PhysRegIndex idx, DynInstPtr &new_inst) 82 { dependGraph[idx].inst = new_inst; } 83 84 /** Clears the producing instruction. */ 85 void clearInst(PhysRegIndex idx) 86 { dependGraph[idx].inst = NULL; } 87 88 /** Removes an instruction from a single linked list. */ 89 void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove); 90 91 /** Removes and returns the newest dependent of a specific register. */ 92 DynInstPtr pop(PhysRegIndex idx); 93 94 /** Checks if there are any dependents on a specific register. */ 95 bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; } 96 97 /** Debugging function to dump out the dependency graph. 98 */ 99 void dump(); 100 101 private: 102 /** Array of linked lists. Each linked list is a list of all the 103 * instructions that depend upon a given register. The actual 104 * register's index is used to index into the graph; ie all 105 * instructions in flight that are dependent upon r34 will be 106 * in the linked list of dependGraph[34]. 107 */ 108 DepEntry *dependGraph; 109 110 /** Number of linked lists; identical to the number of registers. */ 111 int numEntries; 112 113 // Debug variable, remove when done testing. 114 unsigned memAllocCounter; 115 116 public: 117 // Debug variable, remove when done testing. 118 uint64_t nodesTraversed; 119 // Debug variable, remove when done testing. 120 uint64_t nodesRemoved; 121}; 122 123template <class DynInstPtr> 124void 125DependencyGraph<DynInstPtr>::resize(int num_entries) 126{ 127 numEntries = num_entries; 128 dependGraph = new DepEntry[numEntries]; 129} 130 131template <class DynInstPtr> 132void 133DependencyGraph<DynInstPtr>::reset() 134{ 135 // Clear the dependency graph 136 DepEntry *curr; 137 DepEntry *prev; 138 139 for (int i = 0; i < numEntries; ++i) { 140 curr = dependGraph[i].next; 141 142 while (curr) { 143 memAllocCounter--; 144 145 prev = curr; 146 curr = prev->next; 147 prev->inst = NULL; 148 149 delete prev; 150 } 151 152 if (dependGraph[i].inst) { 153 dependGraph[i].inst = NULL; 154 } 155 156 dependGraph[i].next = NULL; 157 } 158} 159 160template <class DynInstPtr> 161void 162DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst) 163{ 164 //Add this new, dependent instruction at the head of the dependency 165 //chain. 166 167 // First create the entry that will be added to the head of the 168 // dependency chain. 169 DepEntry *new_entry = new DepEntry; 170 new_entry->next = dependGraph[idx].next; 171 new_entry->inst = new_inst; 172 173 // Then actually add it to the chain. 174 dependGraph[idx].next = new_entry; 175 176 ++memAllocCounter; 177} 178 179 180template <class DynInstPtr> 181void 182DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx, 183 DynInstPtr &inst_to_remove) 184{ 185 DepEntry *prev = &dependGraph[idx]; 186 DepEntry *curr = dependGraph[idx].next; 187 188 // Make sure curr isn't NULL. Because this instruction is being 189 // removed from a dependency list, it must have been placed there at 190 // an earlier time. The dependency chain should not be empty, 191 // unless the instruction dependent upon it is already ready. 192 if (curr == NULL) { 193 return; 194 } 195 196 nodesRemoved++; 197 198 // Find the instruction to remove within the dependency linked list. 199 while (curr->inst != inst_to_remove) { 200 prev = curr; 201 curr = curr->next; 202 nodesTraversed++; 203 204 assert(curr != NULL); 205 } 206 207 // Now remove this instruction from the list. 208 prev->next = curr->next; 209 210 --memAllocCounter; 211 212 // Could push this off to the destructor of DependencyEntry 213 curr->inst = NULL; 214 215 delete curr; 216} 217 218template <class DynInstPtr> 219DynInstPtr 220DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx) 221{ 222 DepEntry *node; 223 node = dependGraph[idx].next; 224 DynInstPtr inst = NULL; 225 if (node) { 226 inst = node->inst; 227 dependGraph[idx].next = node->next; 228 node->inst = NULL; 229 memAllocCounter--; 230 delete node; 231 } 232 return inst; 233} 234 235template <class DynInstPtr> 236void 237DependencyGraph<DynInstPtr>::dump() 238{ 239 DepEntry *curr; 240 241 for (int i = 0; i < numEntries; ++i) 242 { 243 curr = &dependGraph[i]; 244 245 if (curr->inst) { 246 cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ", 247 i, curr->inst->readPC(), curr->inst->seqNum); 248 } else { 249 cprintf("dependGraph[%i]: No producer. consumer: ", i); 250 } 251 252 while (curr->next != NULL) { 253 curr = curr->next; 254 255 cprintf("%#x [sn:%lli] ", 256 curr->inst->readPC(), curr->inst->seqNum); 257 } 258 259 cprintf("\n"); 260 } 261 cprintf("memAllocCounter: %i\n", memAllocCounter); 262} 263 264#endif // __CPU_O3_DEP_GRAPH_HH__
|