dep_graph.hh revision 9444 
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, DynInstPtr &new_inst);
93
94    /** Sets the producing instruction of a given register. */
95    void setInst(PhysRegIndex idx, 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, 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, DynInstPtr &new_inst)
186{
187    //Add this new, dependent instruction at the head of the dependency
188    //chain.
189
190    // First create the entry that will be added to the head of the
191    // dependency chain.
192    DepEntry *new_entry = new DepEntry;
193    new_entry->next = dependGraph[idx].next;
194    new_entry->inst = new_inst;
195
196    // Then actually add it to the chain.
197    dependGraph[idx].next = new_entry;
198
199    ++memAllocCounter;
200}
201
202
203template <class DynInstPtr>
204void
205DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
206                                    DynInstPtr &inst_to_remove)
207{
208    DepEntry *prev = &dependGraph[idx];
209    DepEntry *curr = dependGraph[idx].next;
210
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.
215    if (curr == NULL) {
216        return;
217    }
218
219    nodesRemoved++;
220
221    // Find the instruction to remove within the dependency linked list.
222    while (curr->inst != inst_to_remove) {
223        prev = curr;
224        curr = curr->next;
225        nodesTraversed++;
226
227        assert(curr != NULL);
228    }
229
230    // Now remove this instruction from the list.
231    prev->next = curr->next;
232
233    --memAllocCounter;
234
235    // Could push this off to the destructor of DependencyEntry
236    curr->inst = NULL;
237
238    delete curr;
239}
240
241template <class DynInstPtr>
242DynInstPtr
243DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx)
244{
245    DepEntry *node;
246    node = dependGraph[idx].next;
247    DynInstPtr inst = NULL;
248    if (node) {
249        inst = node->inst;
250        dependGraph[idx].next = node->next;
251        node->inst = NULL;
252        memAllocCounter--;
253        delete node;
254    }
255    return inst;
256}
257
258template <class DynInstPtr>
259bool
260DependencyGraph<DynInstPtr>::empty() const
261{
262    for (int i = 0; i < numEntries; ++i) {
263        if (!empty(i))
264            return false;
265    }
266    return true;
267}
268
269template <class DynInstPtr>
270void
271DependencyGraph<DynInstPtr>::dump()
272{
273    DepEntry *curr;
274
275    for (int i = 0; i < numEntries; ++i)
276    {
277        curr = &dependGraph[i];
278
279        if (curr->inst) {
280            cprintf("dependGraph[%i]: producer: %s [sn:%lli] consumer: ",
281                    i, curr->inst->pcState(), curr->inst->seqNum);
282        } else {
283            cprintf("dependGraph[%i]: No producer. consumer: ", i);
284        }
285
286        while (curr->next != NULL) {
287            curr = curr->next;
288
289            cprintf("%s [sn:%lli] ",
290                    curr->inst->pcState(), curr->inst->seqNum);
291        }
292
293        cprintf("\n");
294    }
295    cprintf("memAllocCounter: %i\n", memAllocCounter);
296}
297
298#endif // __CPU_O3_DEP_GRAPH_HH__
299