store_set.cc revision 2348
113465Sgabeblack@google.com/* 213465Sgabeblack@google.com * Copyright (c) 2004-2006 The Regents of The University of Michigan 313465Sgabeblack@google.com * All rights reserved. 413465Sgabeblack@google.com * 513465Sgabeblack@google.com * Redistribution and use in source and binary forms, with or without 613465Sgabeblack@google.com * modification, are permitted provided that the following conditions are 713465Sgabeblack@google.com * met: redistributions of source code must retain the above copyright 813465Sgabeblack@google.com * notice, this list of conditions and the following disclaimer; 913465Sgabeblack@google.com * redistributions in binary form must reproduce the above copyright 1013465Sgabeblack@google.com * notice, this list of conditions and the following disclaimer in the 1113465Sgabeblack@google.com * documentation and/or other materials provided with the distribution; 1213465Sgabeblack@google.com * neither the name of the copyright holders nor the names of its 1313465Sgabeblack@google.com * contributors may be used to endorse or promote products derived from 1413465Sgabeblack@google.com * this software without specific prior written permission. 1513465Sgabeblack@google.com * 1613465Sgabeblack@google.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1713465Sgabeblack@google.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1813465Sgabeblack@google.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1913465Sgabeblack@google.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2013465Sgabeblack@google.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2113465Sgabeblack@google.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2213465Sgabeblack@google.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2313465Sgabeblack@google.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2413465Sgabeblack@google.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2513465Sgabeblack@google.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2613465Sgabeblack@google.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2713465Sgabeblack@google.com */ 2813465Sgabeblack@google.com 2913465Sgabeblack@google.com#include "base/intmath.hh" 3013465Sgabeblack@google.com#include "base/trace.hh" 3113465Sgabeblack@google.com#include "cpu/o3/store_set.hh" 3213465Sgabeblack@google.com 3313465Sgabeblack@google.comStoreSet::StoreSet(int _SSIT_size, int _LFST_size) 3413465Sgabeblack@google.com : SSITSize(_SSIT_size), LFSTSize(_LFST_size) 3513465Sgabeblack@google.com{ 3613465Sgabeblack@google.com DPRINTF(StoreSet, "StoreSet: Creating store set object.\n"); 3713465Sgabeblack@google.com DPRINTF(StoreSet, "StoreSet: SSIT size: %i, LFST size: %i.\n", 3813465Sgabeblack@google.com SSITSize, LFSTSize); 3913465Sgabeblack@google.com 4013465Sgabeblack@google.com if (!isPowerOf2(SSITSize)) { 4113465Sgabeblack@google.com fatal("Invalid SSIT size!\n"); 4213465Sgabeblack@google.com } 4313465Sgabeblack@google.com 4413465Sgabeblack@google.com SSIT.resize(SSITSize); 4513465Sgabeblack@google.com 4613465Sgabeblack@google.com validSSIT.resize(SSITSize); 4713465Sgabeblack@google.com 4813465Sgabeblack@google.com for (int i = 0; i < SSITSize; ++i) 4913465Sgabeblack@google.com validSSIT[i] = false; 5013465Sgabeblack@google.com 5113465Sgabeblack@google.com if (!isPowerOf2(LFSTSize)) { 5213465Sgabeblack@google.com fatal("Invalid LFST size!\n"); 5313465Sgabeblack@google.com } 5413465Sgabeblack@google.com 5513465Sgabeblack@google.com LFST.resize(LFSTSize); 5613465Sgabeblack@google.com 5713465Sgabeblack@google.com validLFST.resize(LFSTSize); 5813465Sgabeblack@google.com 5913465Sgabeblack@google.com for (int i = 0; i < LFSTSize; ++i) { 6013465Sgabeblack@google.com validLFST[i] = false; 6113465Sgabeblack@google.com LFST[i] = 0; 6213465Sgabeblack@google.com } 6313465Sgabeblack@google.com 6413465Sgabeblack@google.com indexMask = SSITSize - 1; 6513465Sgabeblack@google.com 6613465Sgabeblack@google.com offsetBits = 2; 6713465Sgabeblack@google.com} 6813465Sgabeblack@google.com 6913465Sgabeblack@google.comStoreSet::~StoreSet() 7013465Sgabeblack@google.com{ 7113465Sgabeblack@google.com} 7213465Sgabeblack@google.com 7313465Sgabeblack@google.comvoid 7413465Sgabeblack@google.comStoreSet::init(int _SSIT_size, int _LFST_size) 7513465Sgabeblack@google.com{ 7613465Sgabeblack@google.com SSITSize = _SSIT_size; 7713465Sgabeblack@google.com LFSTSize = _LFST_size; 7813465Sgabeblack@google.com 7913465Sgabeblack@google.com DPRINTF(StoreSet, "StoreSet: Creating store set object.\n"); 8013465Sgabeblack@google.com DPRINTF(StoreSet, "StoreSet: SSIT size: %i, LFST size: %i.\n", 8113465Sgabeblack@google.com SSITSize, LFSTSize); 8213465Sgabeblack@google.com 8313465Sgabeblack@google.com SSIT.resize(SSITSize); 8413465Sgabeblack@google.com 8513465Sgabeblack@google.com validSSIT.resize(SSITSize); 8613465Sgabeblack@google.com 8713465Sgabeblack@google.com for (int i = 0; i < SSITSize; ++i) 8813465Sgabeblack@google.com validSSIT[i] = false; 8913465Sgabeblack@google.com 9013465Sgabeblack@google.com LFST.resize(LFSTSize); 9113465Sgabeblack@google.com 9213465Sgabeblack@google.com validLFST.resize(LFSTSize); 9313465Sgabeblack@google.com 9413465Sgabeblack@google.com for (int i = 0; i < LFSTSize; ++i) { 9513465Sgabeblack@google.com validLFST[i] = false; 9613465Sgabeblack@google.com LFST[i] = 0; 9713465Sgabeblack@google.com } 9813465Sgabeblack@google.com 9913465Sgabeblack@google.com indexMask = SSITSize - 1; 10013465Sgabeblack@google.com 10113465Sgabeblack@google.com offsetBits = 2; 10213465Sgabeblack@google.com} 10313465Sgabeblack@google.com 10413465Sgabeblack@google.com 10513465Sgabeblack@google.comvoid 10613465Sgabeblack@google.comStoreSet::violation(Addr store_PC, Addr load_PC) 10713465Sgabeblack@google.com{ 10813465Sgabeblack@google.com int load_index = calcIndex(load_PC); 10913465Sgabeblack@google.com int store_index = calcIndex(store_PC); 11013465Sgabeblack@google.com 11113465Sgabeblack@google.com assert(load_index < SSITSize && store_index < SSITSize); 11213465Sgabeblack@google.com 11313465Sgabeblack@google.com bool valid_load_SSID = validSSIT[load_index]; 11413465Sgabeblack@google.com bool valid_store_SSID = validSSIT[store_index]; 11513465Sgabeblack@google.com 11613465Sgabeblack@google.com if (!valid_load_SSID && !valid_store_SSID) { 11713465Sgabeblack@google.com // Calculate a new SSID here. 11813465Sgabeblack@google.com SSID new_set = calcSSID(load_PC); 11913465Sgabeblack@google.com 12013465Sgabeblack@google.com validSSIT[load_index] = true; 12113465Sgabeblack@google.com 122 SSIT[load_index] = new_set; 123 124 validSSIT[store_index] = true; 125 126 SSIT[store_index] = new_set; 127 128 assert(new_set < LFSTSize); 129 130 DPRINTF(StoreSet, "StoreSet: Neither load nor store had a valid " 131 "storeset, creating a new one: %i for load %#x, store %#x\n", 132 new_set, load_PC, store_PC); 133 } else if (valid_load_SSID && !valid_store_SSID) { 134 SSID load_SSID = SSIT[load_index]; 135 136 validSSIT[store_index] = true; 137 138 SSIT[store_index] = load_SSID; 139 140 assert(load_SSID < LFSTSize); 141 142 DPRINTF(StoreSet, "StoreSet: Load had a valid store set. Adding " 143 "store to that set: %i for load %#x, store %#x\n", 144 load_SSID, load_PC, store_PC); 145 } else if (!valid_load_SSID && valid_store_SSID) { 146 SSID store_SSID = SSIT[store_index]; 147 148 validSSIT[load_index] = true; 149 150 SSIT[load_index] = store_SSID; 151 152 DPRINTF(StoreSet, "StoreSet: Store had a valid store set: %i for " 153 "load %#x, store %#x\n", 154 store_SSID, load_PC, store_PC); 155 } else { 156 SSID load_SSID = SSIT[load_index]; 157 SSID store_SSID = SSIT[store_index]; 158 159 assert(load_SSID < LFSTSize && store_SSID < LFSTSize); 160 161 // The store set with the lower number wins 162 if (store_SSID > load_SSID) { 163 SSIT[store_index] = load_SSID; 164 165 DPRINTF(StoreSet, "StoreSet: Load had smaller store set: %i; " 166 "for load %#x, store %#x\n", 167 load_SSID, load_PC, store_PC); 168 } else { 169 SSIT[load_index] = store_SSID; 170 171 DPRINTF(StoreSet, "StoreSet: Store had smaller store set: %i; " 172 "for load %#x, store %#x\n", 173 store_SSID, load_PC, store_PC); 174 } 175 } 176} 177 178void 179StoreSet::insertLoad(Addr load_PC, InstSeqNum load_seq_num) 180{ 181 // Does nothing. 182 return; 183} 184 185void 186StoreSet::insertStore(Addr store_PC, InstSeqNum store_seq_num, 187 unsigned tid) 188{ 189 int index = calcIndex(store_PC); 190 191 int store_SSID; 192 193 assert(index < SSITSize); 194 195 if (!validSSIT[index]) { 196 // Do nothing if there's no valid entry. 197 return; 198 } else { 199 store_SSID = SSIT[index]; 200 201 assert(store_SSID < LFSTSize); 202 203 // Update the last store that was fetched with the current one. 204 LFST[store_SSID] = store_seq_num; 205 206 validLFST[store_SSID] = 1; 207 208 storeList[store_seq_num] = store_SSID; 209 210 DPRINTF(StoreSet, "Store %#x updated the LFST, SSID: %i\n", 211 store_PC, store_SSID); 212 } 213} 214 215InstSeqNum 216StoreSet::checkInst(Addr PC) 217{ 218 int index = calcIndex(PC); 219 220 int inst_SSID; 221 222 assert(index < SSITSize); 223 224 if (!validSSIT[index]) { 225 DPRINTF(StoreSet, "Inst %#x with index %i had no SSID\n", 226 PC, index); 227 228 // Return 0 if there's no valid entry. 229 return 0; 230 } else { 231 inst_SSID = SSIT[index]; 232 233 assert(inst_SSID < LFSTSize); 234 235 if (!validLFST[inst_SSID]) { 236 237 DPRINTF(StoreSet, "Inst %#x with index %i and SSID %i had no " 238 "dependency\n", PC, index, inst_SSID); 239 240 return 0; 241 } else { 242 DPRINTF(StoreSet, "Inst %#x with index %i and SSID %i had LFST " 243 "inum of %i\n", PC, index, inst_SSID, LFST[inst_SSID]); 244 245 return LFST[inst_SSID]; 246 } 247 } 248} 249 250void 251StoreSet::issued(Addr issued_PC, InstSeqNum issued_seq_num, bool is_store) 252{ 253 // This only is updated upon a store being issued. 254 if (!is_store) { 255 return; 256 } 257 258 int index = calcIndex(issued_PC); 259 260 int store_SSID; 261 262 assert(index < SSITSize); 263 264 SeqNumMapIt store_list_it = storeList.find(issued_seq_num); 265 266 if (store_list_it != storeList.end()) { 267 storeList.erase(store_list_it); 268 } 269 270 // Make sure the SSIT still has a valid entry for the issued store. 271 if (!validSSIT[index]) { 272 return; 273 } 274 275 store_SSID = SSIT[index]; 276 277 assert(store_SSID < LFSTSize); 278 279 // If the last fetched store in the store set refers to the store that 280 // was just issued, then invalidate the entry. 281 if (validLFST[store_SSID] && LFST[store_SSID] == issued_seq_num) { 282 DPRINTF(StoreSet, "StoreSet: store invalidated itself in LFST.\n"); 283 validLFST[store_SSID] = false; 284 } 285} 286 287void 288StoreSet::squash(InstSeqNum squashed_num, unsigned tid) 289{ 290 DPRINTF(StoreSet, "StoreSet: Squashing until inum %i\n", 291 squashed_num); 292 293 int idx; 294 SeqNumMapIt store_list_it = storeList.begin(); 295 296 //@todo:Fix to only delete from correct thread 297 while (!storeList.empty()) { 298 idx = (*store_list_it).second; 299 300 if ((*store_list_it).first <= squashed_num) { 301 break; 302 } 303 304 bool younger = LFST[idx] > squashed_num; 305 306 if (validLFST[idx] && younger) { 307 DPRINTF(StoreSet, "Squashed [sn:%lli]\n", LFST[idx]); 308 validLFST[idx] = false; 309 310 storeList.erase(store_list_it++); 311 } else if (!validLFST[idx] && younger) { 312 storeList.erase(store_list_it++); 313 } 314 } 315} 316 317void 318StoreSet::clear() 319{ 320 for (int i = 0; i < SSITSize; ++i) { 321 validSSIT[i] = false; 322 } 323 324 for (int i = 0; i < LFSTSize; ++i) { 325 validLFST[i] = false; 326 } 327 328 storeList.clear(); 329} 330 331void 332StoreSet::dump() 333{ 334 cprintf("storeList.size(): %i\n", storeList.size()); 335 SeqNumMapIt store_list_it = storeList.begin(); 336 337 int num = 0; 338 339 while (store_list_it != storeList.end()) { 340 cprintf("%i: [sn:%lli] SSID:%i\n", 341 num, (*store_list_it).first, (*store_list_it).second); 342 num++; 343 store_list_it++; 344 } 345} 346