store_set.hh revision 8519:ef35ce2bd73f
15443Sgblack@eecs.umich.edu/* 25443Sgblack@eecs.umich.edu * Copyright (c) 2004-2005 The Regents of The University of Michigan 35443Sgblack@eecs.umich.edu * All rights reserved. 45443Sgblack@eecs.umich.edu * 55443Sgblack@eecs.umich.edu * Redistribution and use in source and binary forms, with or without 65443Sgblack@eecs.umich.edu * modification, are permitted provided that the following conditions are 75443Sgblack@eecs.umich.edu * met: redistributions of source code must retain the above copyright 85443Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer; 95443Sgblack@eecs.umich.edu * redistributions in binary form must reproduce the above copyright 105443Sgblack@eecs.umich.edu * notice, this list of conditions and the following disclaimer in the 115443Sgblack@eecs.umich.edu * documentation and/or other materials provided with the distribution; 125443Sgblack@eecs.umich.edu * neither the name of the copyright holders nor the names of its 135443Sgblack@eecs.umich.edu * contributors may be used to endorse or promote products derived from 145443Sgblack@eecs.umich.edu * this software without specific prior written permission. 155443Sgblack@eecs.umich.edu * 165443Sgblack@eecs.umich.edu * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 175443Sgblack@eecs.umich.edu * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 185443Sgblack@eecs.umich.edu * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 195443Sgblack@eecs.umich.edu * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 205443Sgblack@eecs.umich.edu * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 215443Sgblack@eecs.umich.edu * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 225443Sgblack@eecs.umich.edu * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 235443Sgblack@eecs.umich.edu * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 245443Sgblack@eecs.umich.edu * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 255443Sgblack@eecs.umich.edu * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 265443Sgblack@eecs.umich.edu * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 275443Sgblack@eecs.umich.edu * 285443Sgblack@eecs.umich.edu * Authors: Kevin Lim 295443Sgblack@eecs.umich.edu */ 305443Sgblack@eecs.umich.edu 315443Sgblack@eecs.umich.edu#ifndef __CPU_O3_STORE_SET_HH__ 325443Sgblack@eecs.umich.edu#define __CPU_O3_STORE_SET_HH__ 335443Sgblack@eecs.umich.edu 345443Sgblack@eecs.umich.edu#include <list> 355443Sgblack@eecs.umich.edu#include <map> 368229Snate@binkert.org#include <utility> 375606Snate@binkert.org#include <vector> 385606Snate@binkert.org 395443Sgblack@eecs.umich.edu#include "base/types.hh" 406216Snate@binkert.org#include "cpu/inst_seq.hh" 419356Snilay@cs.wisc.edu 428232Snate@binkert.orgstruct ltseqnum { 439356Snilay@cs.wisc.edu bool operator()(const InstSeqNum &lhs, const InstSeqNum &rhs) const 445443Sgblack@eecs.umich.edu { 455443Sgblack@eecs.umich.edu return lhs > rhs; 465443Sgblack@eecs.umich.edu } 475606Snate@binkert.org}; 485443Sgblack@eecs.umich.edu 495635Sgblack@eecs.umich.edu/** 505443Sgblack@eecs.umich.edu * Implements a store set predictor for determining if memory 515443Sgblack@eecs.umich.edu * instructions are dependent upon each other. See paper "Memory 525443Sgblack@eecs.umich.edu * Dependence Prediction using Store Sets" by Chrysos and Emer. SSID 535443Sgblack@eecs.umich.edu * stands for Store Set ID, SSIT stands for Store Set ID Table, and 545443Sgblack@eecs.umich.edu * LFST is Last Fetched Store Table. 555443Sgblack@eecs.umich.edu */ 565443Sgblack@eecs.umich.educlass StoreSet 575443Sgblack@eecs.umich.edu{ 585443Sgblack@eecs.umich.edu public: 595443Sgblack@eecs.umich.edu typedef unsigned SSID; 605443Sgblack@eecs.umich.edu 615443Sgblack@eecs.umich.edu public: 625443Sgblack@eecs.umich.edu /** Default constructor. init() must be called prior to use. */ 635443Sgblack@eecs.umich.edu StoreSet() { }; 645443Sgblack@eecs.umich.edu 655443Sgblack@eecs.umich.edu /** Creates store set predictor with given table sizes. */ 665443Sgblack@eecs.umich.edu StoreSet(uint64_t clear_period, int SSIT_size, int LFST_size); 675443Sgblack@eecs.umich.edu 685443Sgblack@eecs.umich.edu /** Default destructor. */ 695443Sgblack@eecs.umich.edu ~StoreSet(); 705443Sgblack@eecs.umich.edu 715443Sgblack@eecs.umich.edu /** Initializes the store set predictor with the given table sizes. */ 725443Sgblack@eecs.umich.edu void init(uint64_t clear_period, int SSIT_size, int LFST_size); 735443Sgblack@eecs.umich.edu 745443Sgblack@eecs.umich.edu /** Records a memory ordering violation between the younger load 755443Sgblack@eecs.umich.edu * and the older store. */ 765443Sgblack@eecs.umich.edu void violation(Addr store_PC, Addr load_PC); 775443Sgblack@eecs.umich.edu 785443Sgblack@eecs.umich.edu /** Clears the store set predictor every so often so that all the 795443Sgblack@eecs.umich.edu * entries aren't used and stores are constantly predicted as 805443Sgblack@eecs.umich.edu * conflicting. 815443Sgblack@eecs.umich.edu */ 825443Sgblack@eecs.umich.edu void checkClear(); 835443Sgblack@eecs.umich.edu 845443Sgblack@eecs.umich.edu /** Inserts a load into the store set predictor. This does nothing but 855443Sgblack@eecs.umich.edu * is included in case other predictors require a similar function. 865443Sgblack@eecs.umich.edu */ 875443Sgblack@eecs.umich.edu void insertLoad(Addr load_PC, InstSeqNum load_seq_num); 885443Sgblack@eecs.umich.edu 895443Sgblack@eecs.umich.edu /** Inserts a store into the store set predictor. Updates the 905443Sgblack@eecs.umich.edu * LFST if the store has a valid SSID. */ 915443Sgblack@eecs.umich.edu void insertStore(Addr store_PC, InstSeqNum store_seq_num, ThreadID tid); 925443Sgblack@eecs.umich.edu 935443Sgblack@eecs.umich.edu /** Checks if the instruction with the given PC is dependent upon 945443Sgblack@eecs.umich.edu * any store. @return Returns the sequence number of the store 955642Sgblack@eecs.umich.edu * instruction this PC is dependent upon. Returns 0 if none. 965443Sgblack@eecs.umich.edu */ 975443Sgblack@eecs.umich.edu InstSeqNum checkInst(Addr PC); 985443Sgblack@eecs.umich.edu 995443Sgblack@eecs.umich.edu /** Records this PC/sequence number as issued. */ 1005443Sgblack@eecs.umich.edu void issued(Addr issued_PC, InstSeqNum issued_seq_num, bool is_store); 1015444Sgblack@eecs.umich.edu 1025444Sgblack@eecs.umich.edu /** Squashes for a specific thread until the given sequence number. */ 1036067Sgblack@eecs.umich.edu void squash(InstSeqNum squashed_num, ThreadID tid); 1046067Sgblack@eecs.umich.edu 1055443Sgblack@eecs.umich.edu /** Resets all tables. */ 1065443Sgblack@eecs.umich.edu void clear(); 1075443Sgblack@eecs.umich.edu 1085443Sgblack@eecs.umich.edu /** Debug function to dump the contents of the store list. */ 1095443Sgblack@eecs.umich.edu void dump(); 1105443Sgblack@eecs.umich.edu 1115642Sgblack@eecs.umich.edu private: 1125642Sgblack@eecs.umich.edu /** Calculates the index into the SSIT based on the PC. */ 1135443Sgblack@eecs.umich.edu inline int calcIndex(Addr PC) 1145443Sgblack@eecs.umich.edu { return (PC >> offsetBits) & indexMask; } 1156067Sgblack@eecs.umich.edu 1166067Sgblack@eecs.umich.edu /** Calculates a Store Set ID based on the PC. */ 1175443Sgblack@eecs.umich.edu inline SSID calcSSID(Addr PC) 1185443Sgblack@eecs.umich.edu { return ((PC ^ (PC >> 10)) % LFSTSize); } 1195443Sgblack@eecs.umich.edu 1205443Sgblack@eecs.umich.edu /** The Store Set ID Table. */ 1215443Sgblack@eecs.umich.edu std::vector<SSID> SSIT; 1225443Sgblack@eecs.umich.edu 1235443Sgblack@eecs.umich.edu /** Bit vector to tell if the SSIT has a valid entry. */ 1245443Sgblack@eecs.umich.edu std::vector<bool> validSSIT; 1255443Sgblack@eecs.umich.edu 1265443Sgblack@eecs.umich.edu /** Last Fetched Store Table. */ 1275443Sgblack@eecs.umich.edu std::vector<InstSeqNum> LFST; 1285443Sgblack@eecs.umich.edu 1295443Sgblack@eecs.umich.edu /** Bit vector to tell if the LFST has a valid entry. */ 1305443Sgblack@eecs.umich.edu std::vector<bool> validLFST; 1315443Sgblack@eecs.umich.edu 1325443Sgblack@eecs.umich.edu /** Map of stores that have been inserted into the store set, but 1335443Sgblack@eecs.umich.edu * not yet issued or squashed. 1345443Sgblack@eecs.umich.edu */ 1355443Sgblack@eecs.umich.edu std::map<InstSeqNum, int, ltseqnum> storeList; 1365443Sgblack@eecs.umich.edu 1375443Sgblack@eecs.umich.edu typedef std::map<InstSeqNum, int, ltseqnum>::iterator SeqNumMapIt; 1385443Sgblack@eecs.umich.edu 1395606Snate@binkert.org /** Number of loads/stores to process before wiping predictor so all 1405606Snate@binkert.org * entries don't get saturated 1415606Snate@binkert.org */ 1425443Sgblack@eecs.umich.edu uint64_t clearPeriod; 1435642Sgblack@eecs.umich.edu 1445443Sgblack@eecs.umich.edu /** Store Set ID Table size, in entries. */ 1455443Sgblack@eecs.umich.edu int SSITSize; 1465443Sgblack@eecs.umich.edu 1475443Sgblack@eecs.umich.edu /** Last Fetched Store Table size, in entries. */ 1486067Sgblack@eecs.umich.edu int LFSTSize; 1496067Sgblack@eecs.umich.edu 1506067Sgblack@eecs.umich.edu /** Mask to obtain the index. */ 1515443Sgblack@eecs.umich.edu int indexMask; 1525443Sgblack@eecs.umich.edu 1535443Sgblack@eecs.umich.edu // HACK: Hardcoded for now. 1545443Sgblack@eecs.umich.edu int offsetBits; 1555443Sgblack@eecs.umich.edu 1565443Sgblack@eecs.umich.edu /** Number of memory operations predicted since last clear of predictor */ 1575443Sgblack@eecs.umich.edu int memOpsPred; 1585443Sgblack@eecs.umich.edu}; 1595443Sgblack@eecs.umich.edu 1605443Sgblack@eecs.umich.edu#endif // __CPU_O3_STORE_SET_HH__ 1615443Sgblack@eecs.umich.edu