2 * Copyright (c) 2012 ARM Limited
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.
14 * Copyright (c) 2006 The Regents of The University of Michigan
15 * All rights reserved.
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.
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.
43 #ifndef __CPU_O3_DEP_GRAPH_HH__
44 #define __CPU_O3_DEP_GRAPH_HH__
46 #include "cpu/o3/comm.hh"
48 /** Node in a linked list. */
49 template <class DynInstPtr>
54 : inst(NULL), next(NULL)
58 //Might want to include data about what arch. register the
59 //dependence is waiting on.
60 DependencyEntry<DynInstPtr> *next;
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.
72 template <class DynInstPtr>
76 typedef DependencyEntry<DynInstPtr> DepEntry;
78 /** Default construction. Must call resize() prior to use. */
80 : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0)
85 /** Resize the dependency graph to have num_entries registers. */
86 void resize(int num_entries);
88 /** Clears all of the linked lists. */
91 /** Inserts an instruction to be dependent on the given index. */
92 void insert(PhysRegIndex idx, const DynInstPtr &new_inst);
94 /** Sets the producing instruction of a given register. */
95 void setInst(PhysRegIndex idx, const DynInstPtr &new_inst)
96 { dependGraph[idx].inst = new_inst; }
98 /** Clears the producing instruction. */
99 void clearInst(PhysRegIndex idx)
100 { dependGraph[idx].inst = NULL; }
102 /** Removes an instruction from a single linked list. */
103 void remove(PhysRegIndex idx, const DynInstPtr &inst_to_remove);
105 /** Removes and returns the newest dependent of a specific register. */
106 DynInstPtr pop(PhysRegIndex idx);
108 /** Checks if the entire dependency graph is empty. */
111 /** Checks if there are any dependents on a specific register. */
112 bool empty(PhysRegIndex idx) const { return !dependGraph[idx].next; }
114 /** Debugging function to dump out the dependency graph.
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].
125 std::vector<DepEntry> dependGraph;
127 /** Number of linked lists; identical to the number of registers. */
130 // Debug variable, remove when done testing.
131 unsigned memAllocCounter;
134 // Debug variable, remove when done testing.
135 uint64_t nodesTraversed;
136 // Debug variable, remove when done testing.
137 uint64_t nodesRemoved;
140 template <class DynInstPtr>
141 DependencyGraph<DynInstPtr>::~DependencyGraph()
145 template <class DynInstPtr>
147 DependencyGraph<DynInstPtr>::resize(int num_entries)
149 numEntries = num_entries;
150 dependGraph.resize(numEntries);
153 template <class DynInstPtr>
155 DependencyGraph<DynInstPtr>::reset()
157 // Clear the dependency graph
161 for (int i = 0; i < numEntries; ++i) {
162 curr = dependGraph[i].next;
174 if (dependGraph[i].inst) {
175 dependGraph[i].inst = NULL;
178 dependGraph[i].next = NULL;
182 template <class DynInstPtr>
184 DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx,
185 const DynInstPtr &new_inst)
187 //Add this new, dependent instruction at the head of the dependency
190 // First create the entry that will be added to the head of the
192 DepEntry *new_entry = new DepEntry;
193 new_entry->next = dependGraph[idx].next;
194 new_entry->inst = new_inst;
196 // Then actually add it to the chain.
197 dependGraph[idx].next = new_entry;
203 template <class DynInstPtr>
205 DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
206 const DynInstPtr &inst_to_remove)
208 DepEntry *prev = &dependGraph[idx];
209 DepEntry *curr = dependGraph[idx].next;
211 // Make sure curr isn't NULL. Because this instruction is being
212 // removed from a dependency list, it must have been placed there at
213 // an earlier time. The dependency chain should not be empty,
214 // unless the instruction dependent upon it is already ready.
221 // Find the instruction to remove within the dependency linked list.
222 while (curr->inst != inst_to_remove) {
227 assert(curr != NULL);
230 // Now remove this instruction from the list.
231 prev->next = curr->next;
235 // Could push this off to the destructor of DependencyEntry
241 template <class DynInstPtr>
243 DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx)
246 node = dependGraph[idx].next;
247 DynInstPtr inst = NULL;
250 dependGraph[idx].next = node->next;
258 template <class DynInstPtr>
260 DependencyGraph<DynInstPtr>::empty() const
262 for (int i = 0; i < numEntries; ++i) {
269 template <class DynInstPtr>
271 DependencyGraph<DynInstPtr>::dump()
275 for (int i = 0; i < numEntries; ++i)
277 curr = &dependGraph[i];
280 cprintf("dependGraph[%i]: producer: %s [sn:%lli] consumer: ",
281 i, curr->inst->pcState(), curr->inst->seqNum);
283 cprintf("dependGraph[%i]: No producer. consumer: ", i);
286 while (curr->next != NULL) {
289 cprintf("%s [sn:%lli] ",
290 curr->inst->pcState(), curr->inst->seqNum);
295 cprintf("memAllocCounter: %i\n", memAllocCounter);
298 #endif // __CPU_O3_DEP_GRAPH_HH__