2 * Copyright (c) 2006 The Regents of The University of Michigan
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.
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.
31 #ifndef __CPU_O3_DEP_GRAPH_HH__
32 #define __CPU_O3_DEP_GRAPH_HH__
34 #include "cpu/o3/comm.hh"
36 /** Node in a linked list. */
37 template <class DynInstPtr>
42 : inst(NULL), next(NULL)
46 //Might want to include data about what arch. register the
47 //dependence is waiting on.
48 DependencyEntry<DynInstPtr> *next;
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.
60 template <class DynInstPtr>
64 typedef DependencyEntry<DynInstPtr> DepEntry;
66 /** Default construction. Must call resize() prior to use. */
68 : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0)
73 /** Resize the dependency graph to have num_entries registers. */
74 void resize(int num_entries);
76 /** Clears all of the linked lists. */
79 /** Inserts an instruction to be dependent on the given index. */
80 void insert(PhysRegIndex idx, DynInstPtr &new_inst);
82 /** Sets the producing instruction of a given register. */
83 void setInst(PhysRegIndex idx, DynInstPtr &new_inst)
84 { dependGraph[idx].inst = new_inst; }
86 /** Clears the producing instruction. */
87 void clearInst(PhysRegIndex idx)
88 { dependGraph[idx].inst = NULL; }
90 /** Removes an instruction from a single linked list. */
91 void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove);
93 /** Removes and returns the newest dependent of a specific register. */
94 DynInstPtr pop(PhysRegIndex idx);
96 /** Checks if there are any dependents on a specific register. */
97 bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; }
99 /** Debugging function to dump out the dependency graph.
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].
110 DepEntry *dependGraph;
112 /** Number of linked lists; identical to the number of registers. */
115 // Debug variable, remove when done testing.
116 unsigned memAllocCounter;
119 // Debug variable, remove when done testing.
120 uint64_t nodesTraversed;
121 // Debug variable, remove when done testing.
122 uint64_t nodesRemoved;
125 template <class DynInstPtr>
126 DependencyGraph<DynInstPtr>::~DependencyGraph()
128 delete [] dependGraph;
131 template <class DynInstPtr>
133 DependencyGraph<DynInstPtr>::resize(int num_entries)
135 numEntries = num_entries;
136 dependGraph = new DepEntry[numEntries];
139 template <class DynInstPtr>
141 DependencyGraph<DynInstPtr>::reset()
143 // Clear the dependency graph
147 for (int i = 0; i < numEntries; ++i) {
148 curr = dependGraph[i].next;
160 if (dependGraph[i].inst) {
161 dependGraph[i].inst = NULL;
164 dependGraph[i].next = NULL;
168 template <class DynInstPtr>
170 DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst)
172 //Add this new, dependent instruction at the head of the dependency
175 // First create the entry that will be added to the head of the
177 DepEntry *new_entry = new DepEntry;
178 new_entry->next = dependGraph[idx].next;
179 new_entry->inst = new_inst;
181 // Then actually add it to the chain.
182 dependGraph[idx].next = new_entry;
188 template <class DynInstPtr>
190 DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
191 DynInstPtr &inst_to_remove)
193 DepEntry *prev = &dependGraph[idx];
194 DepEntry *curr = dependGraph[idx].next;
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.
206 // Find the instruction to remove within the dependency linked list.
207 while (curr->inst != inst_to_remove) {
212 assert(curr != NULL);
215 // Now remove this instruction from the list.
216 prev->next = curr->next;
220 // Could push this off to the destructor of DependencyEntry
226 template <class DynInstPtr>
228 DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx)
231 node = dependGraph[idx].next;
232 DynInstPtr inst = NULL;
235 dependGraph[idx].next = node->next;
243 template <class DynInstPtr>
245 DependencyGraph<DynInstPtr>::dump()
249 for (int i = 0; i < numEntries; ++i)
251 curr = &dependGraph[i];
254 cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ",
255 i, curr->inst->readPC(), curr->inst->seqNum);
257 cprintf("dependGraph[%i]: No producer. consumer: ", i);
260 while (curr->next != NULL) {
263 cprintf("%#x [sn:%lli] ",
264 curr->inst->readPC(), curr->inst->seqNum);
269 cprintf("memAllocCounter: %i\n", memAllocCounter);
272 #endif // __CPU_O3_DEP_GRAPH_HH__