gem5  v21.1.0.2
dep_graph.hh
Go to the documentation of this file.
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 namespace gem5
47 {
48 
49 namespace o3
50 {
51 
53 template <class DynInstPtr>
55 {
56  public:
58  : inst(NULL), next(NULL)
59  { }
60 
62  //Might want to include data about what arch. register the
63  //dependence is waiting on.
65 };
66 
76 template <class DynInstPtr>
78 {
79  public:
81 
85  { }
86 
88 
90  void resize(int num_entries);
91 
93  void reset();
94 
96  void insert(RegIndex idx, const DynInstPtr &new_inst);
97 
99  void setInst(RegIndex idx, const DynInstPtr &new_inst)
100  { dependGraph[idx].inst = new_inst; }
101 
103  void clearInst(RegIndex idx)
104  { dependGraph[idx].inst = NULL; }
105 
107  void remove(RegIndex idx, const DynInstPtr &inst_to_remove);
108 
110  DynInstPtr pop(RegIndex idx);
111 
113  bool empty() const;
114 
116  bool empty(RegIndex idx) const { return !dependGraph[idx].next; }
117 
120  void dump();
121 
122  private:
130 
133 
134  // Debug variable, remove when done testing.
135  unsigned memAllocCounter;
136 
137  public:
138  // Debug variable, remove when done testing.
139  uint64_t nodesTraversed;
140  // Debug variable, remove when done testing.
141  uint64_t nodesRemoved;
142 };
143 
144 template <class DynInstPtr>
146 {
147 }
148 
149 template <class DynInstPtr>
150 void
152 {
153  numEntries = num_entries;
154  dependGraph.resize(numEntries);
155 }
156 
157 template <class DynInstPtr>
158 void
160 {
161  // Clear the dependency graph
162  DepEntry *curr;
163  DepEntry *prev;
164 
165  for (int i = 0; i < numEntries; ++i) {
166  curr = dependGraph[i].next;
167 
168  while (curr) {
169  memAllocCounter--;
170 
171  prev = curr;
172  curr = prev->next;
173  prev->inst = NULL;
174 
175  delete prev;
176  }
177 
178  if (dependGraph[i].inst) {
179  dependGraph[i].inst = NULL;
180  }
181 
182  dependGraph[i].next = NULL;
183  }
184 }
185 
186 template <class DynInstPtr>
187 void
189 {
190  //Add this new, dependent instruction at the head of the dependency
191  //chain.
192 
193  // First create the entry that will be added to the head of the
194  // dependency chain.
195  DepEntry *new_entry = new DepEntry;
196  new_entry->next = dependGraph[idx].next;
197  new_entry->inst = new_inst;
198 
199  // Then actually add it to the chain.
200  dependGraph[idx].next = new_entry;
201 
202  ++memAllocCounter;
203 }
204 
205 
206 template <class DynInstPtr>
207 void
209  const DynInstPtr &inst_to_remove)
210 {
211  DepEntry *prev = &dependGraph[idx];
212  DepEntry *curr = dependGraph[idx].next;
213 
214  // Make sure curr isn't NULL. Because this instruction is being
215  // removed from a dependency list, it must have been placed there at
216  // an earlier time. The dependency chain should not be empty,
217  // unless the instruction dependent upon it is already ready.
218  if (curr == NULL) {
219  return;
220  }
221 
222  nodesRemoved++;
223 
224  // Find the instruction to remove within the dependency linked list.
225  while (curr->inst != inst_to_remove) {
226  prev = curr;
227  curr = curr->next;
228  nodesTraversed++;
229 
230  assert(curr != NULL);
231  }
232 
233  // Now remove this instruction from the list.
234  prev->next = curr->next;
235 
236  --memAllocCounter;
237 
238  // Could push this off to the destructor of DependencyEntry
239  curr->inst = NULL;
240 
241  delete curr;
242 }
243 
244 template <class DynInstPtr>
247 {
248  DepEntry *node;
249  node = dependGraph[idx].next;
250  DynInstPtr inst = NULL;
251  if (node) {
252  inst = node->inst;
253  dependGraph[idx].next = node->next;
254  node->inst = NULL;
255  memAllocCounter--;
256  delete node;
257  }
258  return inst;
259 }
260 
261 template <class DynInstPtr>
262 bool
264 {
265  for (int i = 0; i < numEntries; ++i) {
266  if (!empty(i))
267  return false;
268  }
269  return true;
270 }
271 
272 template <class DynInstPtr>
273 void
275 {
276  DepEntry *curr;
277 
278  for (int i = 0; i < numEntries; ++i)
279  {
280  curr = &dependGraph[i];
281 
282  if (curr->inst) {
283  cprintf("dependGraph[%i]: producer: %s [sn:%lli] consumer: ",
284  i, curr->inst->pcState(), curr->inst->seqNum);
285  } else {
286  cprintf("dependGraph[%i]: No producer. consumer: ", i);
287  }
288 
289  while (curr->next != NULL) {
290  curr = curr->next;
291 
292  cprintf("%s [sn:%lli] ",
293  curr->inst->pcState(), curr->inst->seqNum);
294  }
295 
296  cprintf("\n");
297  }
298  cprintf("memAllocCounter: %i\n", memAllocCounter);
299 }
300 
301 } // namespace o3
302 } // namespace gem5
303 
304 #endif // __CPU_O3_DEP_GRAPH_HH__
gem5::o3::DependencyGraph::insert
void insert(RegIndex idx, const DynInstPtr &new_inst)
Inserts an instruction to be dependent on the given index.
Definition: dep_graph.hh:188
gem5::o3::DependencyGraph::dependGraph
std::vector< DepEntry > dependGraph
Array of linked lists.
Definition: dep_graph.hh:129
gem5::cprintf
void cprintf(const char *format, const Args &...args)
Definition: cprintf.hh:155
gem5::o3::DependencyGraph::setInst
void setInst(RegIndex idx, const DynInstPtr &new_inst)
Sets the producing instruction of a given register.
Definition: dep_graph.hh:99
gem5::o3::DependencyGraph
Array of linked list that maintains the dependencies between producing instructions and consuming ins...
Definition: dep_graph.hh:77
gem5::o3::DependencyGraph::clearInst
void clearInst(RegIndex idx)
Clears the producing instruction.
Definition: dep_graph.hh:103
gem5::o3::DynInst::seqNum
InstSeqNum seqNum
The sequence number of the instruction.
Definition: dyn_inst.hh:102
std::vector
STL vector class.
Definition: stl.hh:37
gem5::o3::DependencyGraph::nodesRemoved
uint64_t nodesRemoved
Definition: dep_graph.hh:141
gem5::ArmISA::i
Bitfield< 7 > i
Definition: misc_types.hh:66
gem5::o3::DependencyEntry
Node in a linked list.
Definition: dep_graph.hh:54
gem5::o3::DependencyGraph::~DependencyGraph
~DependencyGraph()
Definition: dep_graph.hh:145
gem5::o3::DependencyEntry::DependencyEntry
DependencyEntry()
Definition: dep_graph.hh:57
gem5::RefCountingPtr< DynInst >
gem5::o3::DependencyGraph::pop
DynInstPtr pop(RegIndex idx)
Removes and returns the newest dependent of a specific register.
Definition: dep_graph.hh:246
comm.hh
gem5::o3::DependencyGraph::reset
void reset()
Clears all of the linked lists.
Definition: dep_graph.hh:159
gem5::o3::DependencyGraph::remove
void remove(RegIndex idx, const DynInstPtr &inst_to_remove)
Removes an instruction from a single linked list.
Definition: dep_graph.hh:208
gem5::o3::DependencyGraph::nodesTraversed
uint64_t nodesTraversed
Definition: dep_graph.hh:139
gem5::o3::DependencyGraph::resize
void resize(int num_entries)
Resize the dependency graph to have num_entries registers.
Definition: dep_graph.hh:151
gem5::o3::DependencyGraph::numEntries
int numEntries
Number of linked lists; identical to the number of registers.
Definition: dep_graph.hh:132
gem5::o3::DependencyGraph::memAllocCounter
unsigned memAllocCounter
Definition: dep_graph.hh:135
gem5::o3::DependencyGraph::empty
bool empty(RegIndex idx) const
Checks if there are any dependents on a specific register.
Definition: dep_graph.hh:116
gem5::o3::DependencyGraph::dump
void dump()
Debugging function to dump out the dependency graph.
Definition: dep_graph.hh:274
gem5::o3::DependencyEntry::inst
DynInstPtr inst
Definition: dep_graph.hh:61
gem5::o3::DependencyGraph::DependencyGraph
DependencyGraph()
Default construction.
Definition: dep_graph.hh:83
gem5::o3::DynInst::pcState
TheISA::PCState pcState() const override
Read the PC state of this instruction.
Definition: dyn_inst.hh:979
gem5::o3::DependencyGraph::empty
bool empty() const
Checks if the entire dependency graph is empty.
Definition: dep_graph.hh:263
gem5::o3::DependencyEntry::next
DependencyEntry< DynInstPtr > * next
Definition: dep_graph.hh:64
gem5::RegIndex
uint16_t RegIndex
Definition: types.hh:176
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::o3::DependencyGraph::DepEntry
DependencyEntry< DynInstPtr > DepEntry
Definition: dep_graph.hh:80

Generated on Tue Sep 21 2021 12:25:04 for gem5 by doxygen 1.8.17