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