src/cpu/o3/dep_graph.hh

   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
  41 #ifndef __CPU_O3_DEP_GRAPH_HH__
  42 #define __CPU_O3_DEP_GRAPH_HH__
  43
  44 #include "cpu/o3/comm.hh"
  45
  46 /** Node in a linked list. */
  47 template <class DynInstPtr>
  48 class DependencyEntry
  49 {
  50   public:
  51     DependencyEntry()
  52         : inst(NULL), next(NULL)
  53     { }
  54
  55     DynInstPtr inst;
  56     //Might want to include data about what arch. register the
  57     //dependence is waiting on.
  58     DependencyEntry<DynInstPtr> *next;
  59 };
  60
  61 /** Array of linked list that maintains the dependencies between
  62  * producing instructions and consuming instructions.  Each linked
  63  * list represents a single physical register, having the future
  64  * producer of the register's value, and all consumers waiting on that
  65  * value on the list.  The head node of each linked list represents
  66  * the producing instruction of that register.  Instructions are put
  67  * on the list upon reaching the IQ, and are removed from the list
  68  * either when the producer completes, or the instruction is squashed.
  69 */
  70 template <class DynInstPtr>
  71 class DependencyGraph
  72 {
  73   public:
  74     typedef DependencyEntry<DynInstPtr> DepEntry;
  75
  76     /** Default construction.  Must call resize() prior to use. */
  77     DependencyGraph()
  78         : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0)
  79     { }
  80
  81     ~DependencyGraph();
  82
  83     /** Resize the dependency graph to have num_entries registers. */
  84     void resize(int num_entries);
  85
  86     /** Clears all of the linked lists. */
  87     void reset();
  88
  89     /** Inserts an instruction to be dependent on the given index. */
  90     void insert(PhysRegIndex idx, const DynInstPtr &new_inst);
  91
  92     /** Sets the producing instruction of a given register. */
  93     void setInst(PhysRegIndex idx, const DynInstPtr &new_inst)
  94     { dependGraph[idx].inst = new_inst; }
  95
  96     /** Clears the producing instruction. */
  97     void clearInst(PhysRegIndex idx)
  98     { dependGraph[idx].inst = NULL; }
  99
 100     /** Removes an instruction from a single linked list. */
 101     void remove(PhysRegIndex idx, const DynInstPtr &inst_to_remove);
 102
 103     /** Removes and returns the newest dependent of a specific register. */
 104     DynInstPtr pop(PhysRegIndex idx);
 105
 106     /** Checks if the entire dependency graph is empty. */
 107     bool empty() const;
 108
 109     /** Checks if there are any dependents on a specific register. */
 110     bool empty(PhysRegIndex idx) const { return !dependGraph[idx].next; }
 111
 112     /** Debugging function to dump out the dependency graph.
 113      */
 114     void dump();
 115
 116   private:
 117     /** Array of linked lists.  Each linked list is a list of all the
 118      *  instructions that depend upon a given register.  The actual
 119      *  register's index is used to index into the graph; ie all
 120      *  instructions in flight that are dependent upon r34 will be
 121      *  in the linked list of dependGraph[34].
 122      */
 123     std::vector<DepEntry> dependGraph;
 124
 125     /** Number of linked lists; identical to the number of registers. */
 126     int numEntries;
 127
 128     // Debug variable, remove when done testing.
 129     unsigned memAllocCounter;
 130
 131   public:
 132     // Debug variable, remove when done testing.
 133     uint64_t nodesTraversed;
 134     // Debug variable, remove when done testing.
 135     uint64_t nodesRemoved;
 136 };
 137
 138 template <class DynInstPtr>
 139 DependencyGraph<DynInstPtr>::~DependencyGraph()
 140 {
 141 }
 142
 143 template <class DynInstPtr>
 144 void
 145 DependencyGraph<DynInstPtr>::resize(int num_entries)
 146 {
 147     numEntries = num_entries;
 148     dependGraph.resize(numEntries);
 149 }
 150
 151 template <class DynInstPtr>
 152 void
 153 DependencyGraph<DynInstPtr>::reset()
 154 {
 155     // Clear the dependency graph
 156     DepEntry *curr;
 157     DepEntry *prev;
 158
 159     for (int i = 0; i < numEntries; ++i) {
 160         curr = dependGraph[i].next;
 161
 162         while (curr) {
 163             memAllocCounter--;
 164
 165             prev = curr;
 166             curr = prev->next;
 167             prev->inst = NULL;
 168
 169             delete prev;
 170         }
 171
 172         if (dependGraph[i].inst) {
 173             dependGraph[i].inst = NULL;
 174         }
 175
 176         dependGraph[i].next = NULL;
 177     }
 178 }
 179
 180 template <class DynInstPtr>
 181 void
 182 DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx,
 183         const DynInstPtr &new_inst)
 184 {
 185     //Add this new, dependent instruction at the head of the dependency
 186     //chain.
 187
 188     // First create the entry that will be added to the head of the
 189     // dependency chain.
 190     DepEntry *new_entry = new DepEntry;
 191     new_entry->next = dependGraph[idx].next;
 192     new_entry->inst = new_inst;
 193
 194     // Then actually add it to the chain.
 195     dependGraph[idx].next = new_entry;
 196
 197     ++memAllocCounter;
 198 }
 199
 200
 201 template <class DynInstPtr>
 202 void
 203 DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
 204                                     const DynInstPtr &inst_to_remove)
 205 {
 206     DepEntry *prev = &dependGraph[idx];
 207     DepEntry *curr = dependGraph[idx].next;
 208
 209     // Make sure curr isn't NULL.  Because this instruction is being
 210     // removed from a dependency list, it must have been placed there at
 211     // an earlier time.  The dependency chain should not be empty,
 212     // unless the instruction dependent upon it is already ready.
 213     if (curr == NULL) {
 214         return;
 215     }
 216
 217     nodesRemoved++;
 218
 219     // Find the instruction to remove within the dependency linked list.
 220     while (curr->inst != inst_to_remove) {
 221         prev = curr;
 222         curr = curr->next;
 223         nodesTraversed++;
 224
 225         assert(curr != NULL);
 226     }
 227
 228     // Now remove this instruction from the list.
 229     prev->next = curr->next;
 230
 231     --memAllocCounter;
 232
 233     // Could push this off to the destructor of DependencyEntry
 234     curr->inst = NULL;
 235
 236     delete curr;
 237 }
 238
 239 template <class DynInstPtr>
 240 DynInstPtr
 241 DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx)
 242 {
 243     DepEntry *node;
 244     node = dependGraph[idx].next;
 245     DynInstPtr inst = NULL;
 246     if (node) {
 247         inst = node->inst;
 248         dependGraph[idx].next = node->next;
 249         node->inst = NULL;
 250         memAllocCounter--;
 251         delete node;
 252     }
 253     return inst;
 254 }
 255
 256 template <class DynInstPtr>
 257 bool
 258 DependencyGraph<DynInstPtr>::empty() const
 259 {
 260     for (int i = 0; i < numEntries; ++i) {
 261         if (!empty(i))
 262             return false;
 263     }
 264     return true;
 265 }
 266
 267 template <class DynInstPtr>
 268 void
 269 DependencyGraph<DynInstPtr>::dump()
 270 {
 271     DepEntry *curr;
 272
 273     for (int i = 0; i < numEntries; ++i)
 274     {
 275         curr = &dependGraph[i];
 276
 277         if (curr->inst) {
 278             cprintf("dependGraph[%i]: producer: %s [sn:%lli] consumer: ",
 279                     i, curr->inst->pcState(), curr->inst->seqNum);
 280         } else {
 281             cprintf("dependGraph[%i]: No producer. consumer: ", i);
 282         }
 283
 284         while (curr->next != NULL) {
 285             curr = curr->next;
 286
 287             cprintf("%s [sn:%lli] ",
 288                     curr->inst->pcState(), curr->inst->seqNum);
 289         }
 290
 291         cprintf("\n");
 292     }
 293     cprintf("memAllocCounter: %i\n", memAllocCounter);
 294 }
 295
 296 #endif // __CPU_O3_DEP_GRAPH_HH__