gem5  v22.1.0.0
store_set.cc
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2004-2006 The Regents of The University of Michigan
3  * All rights reserved.
4  *
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.
15  *
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.
27  */
28 
29 #include "cpu/o3/store_set.hh"
30 
31 #include "base/intmath.hh"
32 #include "base/logging.hh"
33 #include "base/trace.hh"
34 #include "debug/StoreSet.hh"
35 
36 namespace gem5
37 {
38 
39 namespace o3
40 {
41 
42 StoreSet::StoreSet(uint64_t clear_period, int _SSIT_size, int _LFST_size)
43  : clearPeriod(clear_period), SSITSize(_SSIT_size), LFSTSize(_LFST_size)
44 {
45  DPRINTF(StoreSet, "StoreSet: Creating store set object.\n");
46  DPRINTF(StoreSet, "StoreSet: SSIT size: %i, LFST size: %i.\n",
48 
49  if (!isPowerOf2(SSITSize)) {
50  fatal("Invalid SSIT size!\n");
51  }
52 
53  SSIT.resize(SSITSize);
54 
55  validSSIT.resize(SSITSize);
56 
57  for (int i = 0; i < SSITSize; ++i)
58  validSSIT[i] = false;
59 
60  if (!isPowerOf2(LFSTSize)) {
61  fatal("Invalid LFST size!\n");
62  }
63 
64  LFST.resize(LFSTSize);
65 
66  validLFST.resize(LFSTSize);
67 
68  for (int i = 0; i < LFSTSize; ++i) {
69  validLFST[i] = false;
70  LFST[i] = 0;
71  }
72 
73  indexMask = SSITSize - 1;
74 
75  offsetBits = 2;
76 
77  memOpsPred = 0;
78 }
79 
81 {
82 }
83 
84 void
85 StoreSet::init(uint64_t clear_period, int _SSIT_size, int _LFST_size)
86 {
87  SSITSize = _SSIT_size;
88  LFSTSize = _LFST_size;
89  clearPeriod = clear_period;
90 
91  DPRINTF(StoreSet, "StoreSet: Creating store set object.\n");
92  DPRINTF(StoreSet, "StoreSet: SSIT size: %i, LFST size: %i.\n",
94 
95  SSIT.resize(SSITSize);
96 
97  validSSIT.resize(SSITSize);
98 
99  for (int i = 0; i < SSITSize; ++i)
100  validSSIT[i] = false;
101 
102  LFST.resize(LFSTSize);
103 
104  validLFST.resize(LFSTSize);
105 
106  for (int i = 0; i < LFSTSize; ++i) {
107  validLFST[i] = false;
108  LFST[i] = 0;
109  }
110 
111  indexMask = SSITSize - 1;
112 
113  offsetBits = 2;
114 
115  memOpsPred = 0;
116 }
117 
118 
119 void
120 StoreSet::violation(Addr store_PC, Addr load_PC)
121 {
122  int load_index = calcIndex(load_PC);
123  int store_index = calcIndex(store_PC);
124 
125  assert(load_index < SSITSize && store_index < SSITSize);
126 
127  bool valid_load_SSID = validSSIT[load_index];
128  bool valid_store_SSID = validSSIT[store_index];
129 
130  if (!valid_load_SSID && !valid_store_SSID) {
131  // Calculate a new SSID here.
132  SSID new_set = calcSSID(load_PC);
133 
134  validSSIT[load_index] = true;
135 
136  SSIT[load_index] = new_set;
137 
138  validSSIT[store_index] = true;
139 
140  SSIT[store_index] = new_set;
141 
142  assert(new_set < LFSTSize);
143 
144  DPRINTF(StoreSet, "StoreSet: Neither load nor store had a valid "
145  "storeset, creating a new one: %i for load %#x, store %#x\n",
146  new_set, load_PC, store_PC);
147  } else if (valid_load_SSID && !valid_store_SSID) {
148  SSID load_SSID = SSIT[load_index];
149 
150  validSSIT[store_index] = true;
151 
152  SSIT[store_index] = load_SSID;
153 
154  assert(load_SSID < LFSTSize);
155 
156  DPRINTF(StoreSet, "StoreSet: Load had a valid store set. Adding "
157  "store to that set: %i for load %#x, store %#x\n",
158  load_SSID, load_PC, store_PC);
159  } else if (!valid_load_SSID && valid_store_SSID) {
160  SSID store_SSID = SSIT[store_index];
161 
162  validSSIT[load_index] = true;
163 
164  SSIT[load_index] = store_SSID;
165 
166  DPRINTF(StoreSet, "StoreSet: Store had a valid store set: %i for "
167  "load %#x, store %#x\n",
168  store_SSID, load_PC, store_PC);
169  } else {
170  SSID load_SSID = SSIT[load_index];
171  SSID store_SSID = SSIT[store_index];
172 
173  assert(load_SSID < LFSTSize && store_SSID < LFSTSize);
174 
175  // The store set with the lower number wins
176  if (store_SSID > load_SSID) {
177  SSIT[store_index] = load_SSID;
178 
179  DPRINTF(StoreSet, "StoreSet: Load had smaller store set: %i; "
180  "for load %#x, store %#x\n",
181  load_SSID, load_PC, store_PC);
182  } else {
183  SSIT[load_index] = store_SSID;
184 
185  DPRINTF(StoreSet, "StoreSet: Store had smaller store set: %i; "
186  "for load %#x, store %#x\n",
187  store_SSID, load_PC, store_PC);
188  }
189  }
190 }
191 
192 void
194 {
195  memOpsPred++;
196  if (memOpsPred > clearPeriod) {
197  DPRINTF(StoreSet, "Wiping predictor state beacuse %d ld/st executed\n",
198  clearPeriod);
199  memOpsPred = 0;
200  clear();
201  }
202 }
203 
204 void
205 StoreSet::insertLoad(Addr load_PC, InstSeqNum load_seq_num)
206 {
207  checkClear();
208  // Does nothing.
209  return;
210 }
211 
212 void
213 StoreSet::insertStore(Addr store_PC, InstSeqNum store_seq_num, ThreadID tid)
214 {
215  int index = calcIndex(store_PC);
216 
217  int store_SSID;
218 
219  checkClear();
220  assert(index < SSITSize);
221 
222  if (!validSSIT[index]) {
223  // Do nothing if there's no valid entry.
224  return;
225  } else {
226  store_SSID = SSIT[index];
227 
228  assert(store_SSID < LFSTSize);
229 
230  // Update the last store that was fetched with the current one.
231  LFST[store_SSID] = store_seq_num;
232 
233  validLFST[store_SSID] = 1;
234 
235  storeList[store_seq_num] = store_SSID;
236 
237  DPRINTF(StoreSet, "Store %#x updated the LFST, SSID: %i\n",
238  store_PC, store_SSID);
239  }
240 }
241 
244 {
245  int index = calcIndex(PC);
246 
247  int inst_SSID;
248 
249  assert(index < SSITSize);
250 
251  if (!validSSIT[index]) {
252  DPRINTF(StoreSet, "Inst %#x with index %i had no SSID\n",
253  PC, index);
254 
255  // Return 0 if there's no valid entry.
256  return 0;
257  } else {
258  inst_SSID = SSIT[index];
259 
260  assert(inst_SSID < LFSTSize);
261 
262  if (!validLFST[inst_SSID]) {
263 
264  DPRINTF(StoreSet, "Inst %#x with index %i and SSID %i had no "
265  "dependency\n", PC, index, inst_SSID);
266 
267  return 0;
268  } else {
269  DPRINTF(StoreSet, "Inst %#x with index %i and SSID %i had LFST "
270  "inum of %i\n", PC, index, inst_SSID, LFST[inst_SSID]);
271 
272  return LFST[inst_SSID];
273  }
274  }
275 }
276 
277 void
278 StoreSet::issued(Addr issued_PC, InstSeqNum issued_seq_num, bool is_store)
279 {
280  // This only is updated upon a store being issued.
281  if (!is_store) {
282  return;
283  }
284 
285  int index = calcIndex(issued_PC);
286 
287  int store_SSID;
288 
289  assert(index < SSITSize);
290 
291  SeqNumMapIt store_list_it = storeList.find(issued_seq_num);
292 
293  if (store_list_it != storeList.end()) {
294  storeList.erase(store_list_it);
295  }
296 
297  // Make sure the SSIT still has a valid entry for the issued store.
298  if (!validSSIT[index]) {
299  return;
300  }
301 
302  store_SSID = SSIT[index];
303 
304  assert(store_SSID < LFSTSize);
305 
306  // If the last fetched store in the store set refers to the store that
307  // was just issued, then invalidate the entry.
308  if (validLFST[store_SSID] && LFST[store_SSID] == issued_seq_num) {
309  DPRINTF(StoreSet, "StoreSet: store invalidated itself in LFST.\n");
310  validLFST[store_SSID] = false;
311  }
312 }
313 
314 void
316 {
317  DPRINTF(StoreSet, "StoreSet: Squashing until inum %i\n",
318  squashed_num);
319 
320  int idx;
321  SeqNumMapIt store_list_it = storeList.begin();
322 
323  //@todo:Fix to only delete from correct thread
324  while (!storeList.empty()) {
325  idx = (*store_list_it).second;
326 
327  if ((*store_list_it).first <= squashed_num) {
328  break;
329  }
330 
331  bool younger = LFST[idx] > squashed_num;
332 
333  if (validLFST[idx] && younger) {
334  DPRINTF(StoreSet, "Squashed [sn:%lli]\n", LFST[idx]);
335  validLFST[idx] = false;
336 
337  storeList.erase(store_list_it++);
338  } else if (!validLFST[idx] && younger) {
339  storeList.erase(store_list_it++);
340  }
341  }
342 }
343 
344 void
346 {
347  for (int i = 0; i < SSITSize; ++i) {
348  validSSIT[i] = false;
349  }
350 
351  for (int i = 0; i < LFSTSize; ++i) {
352  validLFST[i] = false;
353  }
354 
355  storeList.clear();
356 }
357 
358 void
360 {
361  cprintf("storeList.size(): %i\n", storeList.size());
362  SeqNumMapIt store_list_it = storeList.begin();
363 
364  int num = 0;
365 
366  while (store_list_it != storeList.end()) {
367  cprintf("%i: [sn:%lli] SSID:%i\n",
368  num, (*store_list_it).first, (*store_list_it).second);
369  num++;
370  store_list_it++;
371  }
372 }
373 
374 } // namespace o3
375 } // namespace gem5
#define DPRINTF(x,...)
Definition: trace.hh:186
Implements a store set predictor for determining if memory instructions are dependent upon each other...
Definition: store_set.hh:63
void insertLoad(Addr load_PC, InstSeqNum load_seq_num)
Inserts a load into the store set predictor.
Definition: store_set.cc:205
void checkClear()
Clears the store set predictor every so often so that all the entries aren't used and stores are cons...
Definition: store_set.cc:193
std::vector< InstSeqNum > LFST
Last Fetched Store Table.
Definition: store_set.hh:133
void squash(InstSeqNum squashed_num, ThreadID tid)
Squashes for a specific thread until the given sequence number.
Definition: store_set.cc:315
uint64_t clearPeriod
Number of loads/stores to process before wiping predictor so all entries don't get saturated.
Definition: store_set.hh:148
std::vector< bool > validSSIT
Bit vector to tell if the SSIT has a valid entry.
Definition: store_set.hh:130
void dump()
Debug function to dump the contents of the store list.
Definition: store_set.cc:359
std::map< InstSeqNum, int, ltseqnum >::iterator SeqNumMapIt
Definition: store_set.hh:143
int indexMask
Mask to obtain the index.
Definition: store_set.hh:157
void clear()
Resets all tables.
Definition: store_set.cc:345
void insertStore(Addr store_PC, InstSeqNum store_seq_num, ThreadID tid)
Inserts a store into the store set predictor.
Definition: store_set.cc:213
~StoreSet()
Default destructor.
Definition: store_set.cc:80
std::vector< SSID > SSIT
The Store Set ID Table.
Definition: store_set.hh:127
SSID calcSSID(Addr PC)
Calculates a Store Set ID based on the PC.
Definition: store_set.hh:123
void init(uint64_t clear_period, int SSIT_size, int LFST_size)
Initializes the store set predictor with the given table sizes.
Definition: store_set.cc:85
std::vector< bool > validLFST
Bit vector to tell if the LFST has a valid entry.
Definition: store_set.hh:136
int LFSTSize
Last Fetched Store Table size, in entries.
Definition: store_set.hh:154
void issued(Addr issued_PC, InstSeqNum issued_seq_num, bool is_store)
Records this PC/sequence number as issued.
Definition: store_set.cc:278
int calcIndex(Addr PC)
Calculates the index into the SSIT based on the PC.
Definition: store_set.hh:119
InstSeqNum checkInst(Addr PC)
Checks if the instruction with the given PC is dependent upon any store.
Definition: store_set.cc:243
int SSITSize
Store Set ID Table size, in entries.
Definition: store_set.hh:151
StoreSet()
Default constructor.
Definition: store_set.hh:69
void violation(Addr store_PC, Addr load_PC)
Records a memory ordering violation between the younger load and the older store.
Definition: store_set.cc:120
std::map< InstSeqNum, int, ltseqnum > storeList
Map of stores that have been inserted into the store set, but not yet issued or squashed.
Definition: store_set.hh:141
int memOpsPred
Number of memory operations predicted since last clear of predictor.
Definition: store_set.hh:163
static constexpr bool isPowerOf2(const T &n)
Definition: intmath.hh:98
#define fatal(...)
This implements a cprintf based fatal() function.
Definition: logging.hh:190
Bitfield< 7 > i
Definition: misc_types.hh:67
Bitfield< 30, 0 > index
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
int16_t ThreadID
Thread index/ID type.
Definition: types.hh:235
void cprintf(const char *format, const Args &...args)
Definition: cprintf.hh:155
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
uint64_t InstSeqNum
Definition: inst_seq.hh:40

Generated on Wed Dec 21 2022 10:22:31 for gem5 by doxygen 1.9.1