src/cpu/o3/dep_graph.hh

   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  */
  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. */
  37 template <class DynInstPtr>
  38 class 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 */
  60 template <class DynInstPtr>
  61 class 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     ~DependencyGraph();
  72
  73     /** Resize the dependency graph to have num_entries registers. */
  74     void resize(int num_entries);
  75
  76     /** Clears all of the linked lists. */
  77     void reset();
  78
  79     /** Inserts an instruction to be dependent on the given index. */
  80     void insert(PhysRegIndex idx, DynInstPtr &new_inst);
  81
  82     /** Sets the producing instruction of a given register. */
  83     void setInst(PhysRegIndex idx, DynInstPtr &new_inst)
  84     { dependGraph[idx].inst = new_inst; }
  85
  86     /** Clears the producing instruction. */
  87     void clearInst(PhysRegIndex idx)
  88     { dependGraph[idx].inst = NULL; }
  89
  90     /** Removes an instruction from a single linked list. */
  91     void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove);
  92
  93     /** Removes and returns the newest dependent of a specific register. */
  94     DynInstPtr pop(PhysRegIndex idx);
  95
  96     /** Checks if there are any dependents on a specific register. */
  97     bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; }
  98
  99     /** Debugging function to dump out the dependency graph.
 100      */
 101     void dump();
 102
 103   private:
 104     /** Array of linked lists.  Each linked list is a list of all the
 105      *  instructions that depend upon a given register.  The actual
 106      *  register's index is used to index into the graph; ie all
 107      *  instructions in flight that are dependent upon r34 will be
 108      *  in the linked list of dependGraph[34].
 109      */
 110     DepEntry *dependGraph;
 111
 112     /** Number of linked lists; identical to the number of registers. */
 113     int numEntries;
 114
 115     // Debug variable, remove when done testing.
 116     unsigned memAllocCounter;
 117
 118   public:
 119     // Debug variable, remove when done testing.
 120     uint64_t nodesTraversed;
 121     // Debug variable, remove when done testing.
 122     uint64_t nodesRemoved;
 123 };
 124
 125 template <class DynInstPtr>
 126 DependencyGraph<DynInstPtr>::~DependencyGraph()
 127 {
 128     delete [] dependGraph;
 129 }
 130
 131 template <class DynInstPtr>
 132 void
 133 DependencyGraph<DynInstPtr>::resize(int num_entries)
 134 {
 135     numEntries = num_entries;
 136     dependGraph = new DepEntry[numEntries];
 137 }
 138
 139 template <class DynInstPtr>
 140 void
 141 DependencyGraph<DynInstPtr>::reset()
 142 {
 143     // Clear the dependency graph
 144     DepEntry *curr;
 145     DepEntry *prev;
 146
 147     for (int i = 0; i < numEntries; ++i) {
 148         curr = dependGraph[i].next;
 149
 150         while (curr) {
 151             memAllocCounter--;
 152
 153             prev = curr;
 154             curr = prev->next;
 155             prev->inst = NULL;
 156
 157             delete prev;
 158         }
 159
 160         if (dependGraph[i].inst) {
 161             dependGraph[i].inst = NULL;
 162         }
 163
 164         dependGraph[i].next = NULL;
 165     }
 166 }
 167
 168 template <class DynInstPtr>
 169 void
 170 DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst)
 171 {
 172     //Add this new, dependent instruction at the head of the dependency
 173     //chain.
 174
 175     // First create the entry that will be added to the head of the
 176     // dependency chain.
 177     DepEntry *new_entry = new DepEntry;
 178     new_entry->next = dependGraph[idx].next;
 179     new_entry->inst = new_inst;
 180
 181     // Then actually add it to the chain.
 182     dependGraph[idx].next = new_entry;
 183
 184     ++memAllocCounter;
 185 }
 186
 187
 188 template <class DynInstPtr>
 189 void
 190 DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
 191                                     DynInstPtr &inst_to_remove)
 192 {
 193     DepEntry *prev = &dependGraph[idx];
 194     DepEntry *curr = dependGraph[idx].next;
 195
 196     // Make sure curr isn't NULL.  Because this instruction is being
 197     // removed from a dependency list, it must have been placed there at
 198     // an earlier time.  The dependency chain should not be empty,
 199     // unless the instruction dependent upon it is already ready.
 200     if (curr == NULL) {
 201         return;
 202     }
 203
 204     nodesRemoved++;
 205
 206     // Find the instruction to remove within the dependency linked list.
 207     while (curr->inst != inst_to_remove) {
 208         prev = curr;
 209         curr = curr->next;
 210         nodesTraversed++;
 211
 212         assert(curr != NULL);
 213     }
 214
 215     // Now remove this instruction from the list.
 216     prev->next = curr->next;
 217
 218     --memAllocCounter;
 219
 220     // Could push this off to the destructor of DependencyEntry
 221     curr->inst = NULL;
 222
 223     delete curr;
 224 }
 225
 226 template <class DynInstPtr>
 227 DynInstPtr
 228 DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx)
 229 {
 230     DepEntry *node;
 231     node = dependGraph[idx].next;
 232     DynInstPtr inst = NULL;
 233     if (node) {
 234         inst = node->inst;
 235         dependGraph[idx].next = node->next;
 236         node->inst = NULL;
 237         memAllocCounter--;
 238         delete node;
 239     }
 240     return inst;
 241 }
 242
 243 template <class DynInstPtr>
 244 void
 245 DependencyGraph<DynInstPtr>::dump()
 246 {
 247     DepEntry *curr;
 248
 249     for (int i = 0; i < numEntries; ++i)
 250     {
 251         curr = &dependGraph[i];
 252
 253         if (curr->inst) {
 254             cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ",
 255                     i, curr->inst->readPC(), curr->inst->seqNum);
 256         } else {
 257             cprintf("dependGraph[%i]: No producer. consumer: ", i);
 258         }
 259
 260         while (curr->next != NULL) {
 261             curr = curr->next;
 262
 263             cprintf("%#x [sn:%lli] ",
 264                     curr->inst->readPC(), curr->inst->seqNum);
 265         }
 266
 267         cprintf("\n");
 268     }
 269     cprintf("memAllocCounter: %i\n", memAllocCounter);
 270 }
 271
 272 #endif // __CPU_O3_DEP_GRAPH_HH__