src/cpu/o3/store_set.cc

   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 StoreSet::StoreSet(uint64_t clear_period, int _SSIT_size, int _LFST_size)
  37     : clearPeriod(clear_period), SSITSize(_SSIT_size), LFSTSize(_LFST_size)
  38 {
  39     DPRINTF(StoreSet, "StoreSet: Creating store set object.\n");
  40     DPRINTF(StoreSet, "StoreSet: SSIT size: %i, LFST size: %i.\n",
  41             SSITSize, LFSTSize);
  42
  43     if (!isPowerOf2(SSITSize)) {
  44         fatal("Invalid SSIT size!\n");
  45     }
  46
  47     SSIT.resize(SSITSize);
  48
  49     validSSIT.resize(SSITSize);
  50
  51     for (int i = 0; i < SSITSize; ++i)
  52         validSSIT[i] = false;
  53
  54     if (!isPowerOf2(LFSTSize)) {
  55         fatal("Invalid LFST size!\n");
  56     }
  57
  58     LFST.resize(LFSTSize);
  59
  60     validLFST.resize(LFSTSize);
  61
  62     for (int i = 0; i < LFSTSize; ++i) {
  63         validLFST[i] = false;
  64         LFST[i] = 0;
  65     }
  66
  67     indexMask = SSITSize - 1;
  68
  69     offsetBits = 2;
  70
  71     memOpsPred = 0;
  72 }
  73
  74 StoreSet::~StoreSet()
  75 {
  76 }
  77
  78 void
  79 StoreSet::init(uint64_t clear_period, int _SSIT_size, int _LFST_size)
  80 {
  81     SSITSize = _SSIT_size;
  82     LFSTSize = _LFST_size;
  83     clearPeriod = clear_period;
  84
  85     DPRINTF(StoreSet, "StoreSet: Creating store set object.\n");
  86     DPRINTF(StoreSet, "StoreSet: SSIT size: %i, LFST size: %i.\n",
  87             SSITSize, LFSTSize);
  88
  89     SSIT.resize(SSITSize);
  90
  91     validSSIT.resize(SSITSize);
  92
  93     for (int i = 0; i < SSITSize; ++i)
  94         validSSIT[i] = false;
  95
  96     LFST.resize(LFSTSize);
  97
  98     validLFST.resize(LFSTSize);
  99
 100     for (int i = 0; i < LFSTSize; ++i) {
 101         validLFST[i] = false;
 102         LFST[i] = 0;
 103     }
 104
 105     indexMask = SSITSize - 1;
 106
 107     offsetBits = 2;
 108
 109     memOpsPred = 0;
 110 }
 111
 112
 113 void
 114 StoreSet::violation(Addr store_PC, Addr load_PC)
 115 {
 116     int load_index = calcIndex(load_PC);
 117     int store_index = calcIndex(store_PC);
 118
 119     assert(load_index < SSITSize && store_index < SSITSize);
 120
 121     bool valid_load_SSID = validSSIT[load_index];
 122     bool valid_store_SSID = validSSIT[store_index];
 123
 124     if (!valid_load_SSID && !valid_store_SSID) {
 125         // Calculate a new SSID here.
 126         SSID new_set = calcSSID(load_PC);
 127
 128         validSSIT[load_index] = true;
 129
 130         SSIT[load_index] = new_set;
 131
 132         validSSIT[store_index] = true;
 133
 134         SSIT[store_index] = new_set;
 135
 136         assert(new_set < LFSTSize);
 137
 138         DPRINTF(StoreSet, "StoreSet: Neither load nor store had a valid "
 139                 "storeset, creating a new one: %i for load %#x, store %#x\n",
 140                 new_set, load_PC, store_PC);
 141     } else if (valid_load_SSID && !valid_store_SSID) {
 142         SSID load_SSID = SSIT[load_index];
 143
 144         validSSIT[store_index] = true;
 145
 146         SSIT[store_index] = load_SSID;
 147
 148         assert(load_SSID < LFSTSize);
 149
 150         DPRINTF(StoreSet, "StoreSet: Load had a valid store set.  Adding "
 151                 "store to that set: %i for load %#x, store %#x\n",
 152                 load_SSID, load_PC, store_PC);
 153     } else if (!valid_load_SSID && valid_store_SSID) {
 154         SSID store_SSID = SSIT[store_index];
 155
 156         validSSIT[load_index] = true;
 157
 158         SSIT[load_index] = store_SSID;
 159
 160         DPRINTF(StoreSet, "StoreSet: Store had a valid store set: %i for "
 161                 "load %#x, store %#x\n",
 162                 store_SSID, load_PC, store_PC);
 163     } else {
 164         SSID load_SSID = SSIT[load_index];
 165         SSID store_SSID = SSIT[store_index];
 166
 167         assert(load_SSID < LFSTSize && store_SSID < LFSTSize);
 168
 169         // The store set with the lower number wins
 170         if (store_SSID > load_SSID) {
 171             SSIT[store_index] = load_SSID;
 172
 173             DPRINTF(StoreSet, "StoreSet: Load had smaller store set: %i; "
 174                     "for load %#x, store %#x\n",
 175                     load_SSID, load_PC, store_PC);
 176         } else {
 177             SSIT[load_index] = store_SSID;
 178
 179             DPRINTF(StoreSet, "StoreSet: Store had smaller store set: %i; "
 180                     "for load %#x, store %#x\n",
 181                     store_SSID, load_PC, store_PC);
 182         }
 183     }
 184 }
 185
 186 void
 187 StoreSet::checkClear()
 188 {
 189     memOpsPred++;
 190     if (memOpsPred > clearPeriod) {
 191         DPRINTF(StoreSet, "Wiping predictor state beacuse %d ld/st executed\n",
 192                 clearPeriod);
 193         memOpsPred = 0;
 194         clear();
 195     }
 196 }
 197
 198 void
 199 StoreSet::insertLoad(Addr load_PC, InstSeqNum load_seq_num)
 200 {
 201     checkClear();
 202     // Does nothing.
 203     return;
 204 }
 205
 206 void
 207 StoreSet::insertStore(Addr store_PC, InstSeqNum store_seq_num, ThreadID tid)
 208 {
 209     int index = calcIndex(store_PC);
 210
 211     int store_SSID;
 212
 213     checkClear();
 214     assert(index < SSITSize);
 215
 216     if (!validSSIT[index]) {
 217         // Do nothing if there's no valid entry.
 218         return;
 219     } else {
 220         store_SSID = SSIT[index];
 221
 222         assert(store_SSID < LFSTSize);
 223
 224         // Update the last store that was fetched with the current one.
 225         LFST[store_SSID] = store_seq_num;
 226
 227         validLFST[store_SSID] = 1;
 228
 229         storeList[store_seq_num] = store_SSID;
 230
 231         DPRINTF(StoreSet, "Store %#x updated the LFST, SSID: %i\n",
 232                 store_PC, store_SSID);
 233     }
 234 }
 235
 236 InstSeqNum
 237 StoreSet::checkInst(Addr PC)
 238 {
 239     int index = calcIndex(PC);
 240
 241     int inst_SSID;
 242
 243     assert(index < SSITSize);
 244
 245     if (!validSSIT[index]) {
 246         DPRINTF(StoreSet, "Inst %#x with index %i had no SSID\n",
 247                 PC, index);
 248
 249         // Return 0 if there's no valid entry.
 250         return 0;
 251     } else {
 252         inst_SSID = SSIT[index];
 253
 254         assert(inst_SSID < LFSTSize);
 255
 256         if (!validLFST[inst_SSID]) {
 257
 258             DPRINTF(StoreSet, "Inst %#x with index %i and SSID %i had no "
 259                     "dependency\n", PC, index, inst_SSID);
 260
 261             return 0;
 262         } else {
 263             DPRINTF(StoreSet, "Inst %#x with index %i and SSID %i had LFST "
 264                     "inum of %i\n", PC, index, inst_SSID, LFST[inst_SSID]);
 265
 266             return LFST[inst_SSID];
 267         }
 268     }
 269 }
 270
 271 void
 272 StoreSet::issued(Addr issued_PC, InstSeqNum issued_seq_num, bool is_store)
 273 {
 274     // This only is updated upon a store being issued.
 275     if (!is_store) {
 276         return;
 277     }
 278
 279     int index = calcIndex(issued_PC);
 280
 281     int store_SSID;
 282
 283     assert(index < SSITSize);
 284
 285     SeqNumMapIt store_list_it = storeList.find(issued_seq_num);
 286
 287     if (store_list_it != storeList.end()) {
 288         storeList.erase(store_list_it);
 289     }
 290
 291     // Make sure the SSIT still has a valid entry for the issued store.
 292     if (!validSSIT[index]) {
 293         return;
 294     }
 295
 296     store_SSID = SSIT[index];
 297
 298     assert(store_SSID < LFSTSize);
 299
 300     // If the last fetched store in the store set refers to the store that
 301     // was just issued, then invalidate the entry.
 302     if (validLFST[store_SSID] && LFST[store_SSID] == issued_seq_num) {
 303         DPRINTF(StoreSet, "StoreSet: store invalidated itself in LFST.\n");
 304         validLFST[store_SSID] = false;
 305     }
 306 }
 307
 308 void
 309 StoreSet::squash(InstSeqNum squashed_num, ThreadID tid)
 310 {
 311     DPRINTF(StoreSet, "StoreSet: Squashing until inum %i\n",
 312             squashed_num);
 313
 314     int idx;
 315     SeqNumMapIt store_list_it = storeList.begin();
 316
 317     //@todo:Fix to only delete from correct thread
 318     while (!storeList.empty()) {
 319         idx = (*store_list_it).second;
 320
 321         if ((*store_list_it).first <= squashed_num) {
 322             break;
 323         }
 324
 325         bool younger = LFST[idx] > squashed_num;
 326
 327         if (validLFST[idx] && younger) {
 328             DPRINTF(StoreSet, "Squashed [sn:%lli]\n", LFST[idx]);
 329             validLFST[idx] = false;
 330
 331             storeList.erase(store_list_it++);
 332         } else if (!validLFST[idx] && younger) {
 333             storeList.erase(store_list_it++);
 334         }
 335     }
 336 }
 337
 338 void
 339 StoreSet::clear()
 340 {
 341     for (int i = 0; i < SSITSize; ++i) {
 342         validSSIT[i] = false;
 343     }
 344
 345     for (int i = 0; i < LFSTSize; ++i) {
 346         validLFST[i] = false;
 347     }
 348
 349     storeList.clear();
 350 }
 351
 352 void
 353 StoreSet::dump()
 354 {
 355     cprintf("storeList.size(): %i\n", storeList.size());
 356     SeqNumMapIt store_list_it = storeList.begin();
 357
 358     int num = 0;
 359
 360     while (store_list_it != storeList.end()) {
 361         cprintf("%i: [sn:%lli] SSID:%i\n",
 362                 num, (*store_list_it).first, (*store_list_it).second);
 363         num++;
 364         store_list_it++;
 365     }
 366 }