dep_graph.hh revision 2326 
1
2#ifndef __CPU_O3_DEP_GRAPH_HH__
3#define __CPU_O3_DEP_GRAPH_HH__
4
5#include "cpu/o3/comm.hh"
6
7template <class DynInstPtr>
8class DependencyEntry
9{
10  public:
11    DependencyEntry()
12        : inst(NULL), next(NULL)
13    { }
14
15    DynInstPtr inst;
16    //Might want to include data about what arch. register the
17    //dependence is waiting on.
18    DependencyEntry<DynInstPtr> *next;
19};
20
21template <class DynInstPtr>
22class DependencyGraph
23{
24  public:
25    typedef DependencyEntry<DynInstPtr> DepEntry;
26
27    DependencyGraph()
28        : numEntries(0), memAllocCounter(0), nodesTraversed(0), nodesRemoved(0)
29    { }
30
31    void resize(int num_entries);
32
33    void reset();
34
35    void insert(PhysRegIndex idx, DynInstPtr &new_inst);
36
37    void setInst(PhysRegIndex idx, DynInstPtr &new_inst)
38    { dependGraph[idx].inst = new_inst; }
39
40    void clearInst(PhysRegIndex idx)
41    { dependGraph[idx].inst = NULL; }
42
43    void remove(PhysRegIndex idx, DynInstPtr &inst_to_remove);
44
45    DynInstPtr pop(PhysRegIndex idx);
46
47    bool empty(PhysRegIndex idx) { return !dependGraph[idx].next; }
48
49    /** Debugging function to dump out the dependency graph.
50     */
51    void dump();
52
53  private:
54    /** Array of linked lists.  Each linked list is a list of all the
55     *  instructions that depend upon a given register.  The actual
56     *  register's index is used to index into the graph; ie all
57     *  instructions in flight that are dependent upon r34 will be
58     *  in the linked list of dependGraph[34].
59     */
60    DepEntry *dependGraph;
61
62    int numEntries;
63
64    // Debug variable, remove when done testing.
65    unsigned memAllocCounter;
66
67  public:
68    uint64_t nodesTraversed;
69    uint64_t nodesRemoved;
70};
71
72template <class DynInstPtr>
73void
74DependencyGraph<DynInstPtr>::resize(int num_entries)
75{
76    numEntries = num_entries;
77    dependGraph = new DepEntry[numEntries];
78}
79
80template <class DynInstPtr>
81void
82DependencyGraph<DynInstPtr>::reset()
83{
84    // Clear the dependency graph
85    DepEntry *curr;
86    DepEntry *prev;
87
88    for (int i = 0; i < numEntries; ++i) {
89        curr = dependGraph[i].next;
90
91        while (curr) {
92            memAllocCounter--;
93
94            prev = curr;
95            curr = prev->next;
96            prev->inst = NULL;
97
98            delete prev;
99        }
100
101        if (dependGraph[i].inst) {
102            dependGraph[i].inst = NULL;
103        }
104
105        dependGraph[i].next = NULL;
106    }
107}
108
109template <class DynInstPtr>
110void
111DependencyGraph<DynInstPtr>::insert(PhysRegIndex idx, DynInstPtr &new_inst)
112{
113    //Add this new, dependent instruction at the head of the dependency
114    //chain.
115
116    // First create the entry that will be added to the head of the
117    // dependency chain.
118    DepEntry *new_entry = new DepEntry;
119    new_entry->next = dependGraph[idx].next;
120    new_entry->inst = new_inst;
121
122    // Then actually add it to the chain.
123    dependGraph[idx].next = new_entry;
124
125    ++memAllocCounter;
126}
127
128
129template <class DynInstPtr>
130void
131DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
132                                    DynInstPtr &inst_to_remove)
133{
134    DepEntry *prev = &dependGraph[idx];
135    DepEntry *curr = dependGraph[idx].next;
136
137    // Make sure curr isn't NULL.  Because this instruction is being
138    // removed from a dependency list, it must have been placed there at
139    // an earlier time.  The dependency chain should not be empty,
140    // unless the instruction dependent upon it is already ready.
141    if (curr == NULL) {
142        return;
143    }
144
145    nodesRemoved++;
146
147    // Find the instruction to remove within the dependency linked list.
148    while (curr->inst != inst_to_remove) {
149        prev = curr;
150        curr = curr->next;
151        nodesTraversed++;
152
153        assert(curr != NULL);
154    }
155
156    // Now remove this instruction from the list.
157    prev->next = curr->next;
158
159    --memAllocCounter;
160
161    // Could push this off to the destructor of DependencyEntry
162    curr->inst = NULL;
163
164    delete curr;
165}
166
167template <class DynInstPtr>
168DynInstPtr
169DependencyGraph<DynInstPtr>::pop(PhysRegIndex idx)
170{
171    DepEntry *node;
172    node = dependGraph[idx].next;
173    DynInstPtr inst = NULL;
174    if (node) {
175        inst = node->inst;
176        dependGraph[idx].next = node->next;
177        node->inst = NULL;
178        memAllocCounter--;
179        delete node;
180    }
181    return inst;
182}
183
184template <class DynInstPtr>
185void
186DependencyGraph<DynInstPtr>::dump()
187{
188    DepEntry *curr;
189
190    for (int i = 0; i < numEntries; ++i)
191    {
192        curr = &dependGraph[i];
193
194        if (curr->inst) {
195            cprintf("dependGraph[%i]: producer: %#x [sn:%lli] consumer: ",
196                    i, curr->inst->readPC(), curr->inst->seqNum);
197        } else {
198            cprintf("dependGraph[%i]: No producer. consumer: ", i);
199        }
200
201        while (curr->next != NULL) {
202            curr = curr->next;
203
204            cprintf("%#x [sn:%lli] ",
205                    curr->inst->readPC(), curr->inst->seqNum);
206        }
207
208        cprintf("\n");
209    }
210    cprintf("memAllocCounter: %i\n", memAllocCounter);
211}
212
213#endif // __CPU_O3_DEP_GRAPH_HH__
214