store_set.hh revision 8519
11689SN/A/* 212106SRekai.GonzalezAlberquilla@arm.com * Copyright (c) 2004-2005 The Regents of The University of Michigan 39913Ssteve.reinhardt@amd.com * All rights reserved. 47854SAli.Saidi@ARM.com * 57854SAli.Saidi@ARM.com * Redistribution and use in source and binary forms, with or without 67854SAli.Saidi@ARM.com * modification, are permitted provided that the following conditions are 77854SAli.Saidi@ARM.com * met: redistributions of source code must retain the above copyright 87854SAli.Saidi@ARM.com * notice, this list of conditions and the following disclaimer; 97854SAli.Saidi@ARM.com * redistributions in binary form must reproduce the above copyright 107854SAli.Saidi@ARM.com * notice, this list of conditions and the following disclaimer in the 117854SAli.Saidi@ARM.com * documentation and/or other materials provided with the distribution; 127854SAli.Saidi@ARM.com * neither the name of the copyright holders nor the names of its 137854SAli.Saidi@ARM.com * contributors may be used to endorse or promote products derived from 147854SAli.Saidi@ARM.com * this software without specific prior written permission. 152329SN/A * 161689SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 171689SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 181689SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 191689SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 201689SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 211689SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 221689SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 231689SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 241689SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 251689SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 261689SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 271689SN/A * 281689SN/A * Authors: Kevin Lim 291689SN/A */ 301689SN/A 311689SN/A#ifndef __CPU_O3_STORE_SET_HH__ 321689SN/A#define __CPU_O3_STORE_SET_HH__ 331689SN/A 341689SN/A#include <list> 351689SN/A#include <map> 361689SN/A#include <utility> 371689SN/A#include <vector> 381689SN/A 391689SN/A#include "base/types.hh" 402665Ssaidi@eecs.umich.edu#include "cpu/inst_seq.hh" 412665Ssaidi@eecs.umich.edu 422935Sksewell@umich.edustruct ltseqnum { 431689SN/A bool operator()(const InstSeqNum &lhs, const InstSeqNum &rhs) const 441689SN/A { 459944Smatt.horsnell@ARM.com return lhs > rhs; 469944Smatt.horsnell@ARM.com } 479944Smatt.horsnell@ARM.com}; 481060SN/A 491060SN/A/** 503773Sgblack@eecs.umich.edu * Implements a store set predictor for determining if memory 516329Sgblack@eecs.umich.edu * instructions are dependent upon each other. See paper "Memory 526658Snate@binkert.org * Dependence Prediction using Store Sets" by Chrysos and Emer. SSID 531717SN/A * stands for Store Set ID, SSIT stands for Store Set ID Table, and 549913Ssteve.reinhardt@amd.com * LFST is Last Fetched Store Table. 558232Snate@binkert.org */ 568232Snate@binkert.orgclass StoreSet 579527SMatt.Horsnell@arm.com{ 585529Snate@binkert.org public: 591060SN/A typedef unsigned SSID; 606221Snate@binkert.org 616221Snate@binkert.org public: 621061SN/A /** Default constructor. init() must be called prior to use. */ 635529Snate@binkert.org StoreSet() { }; 644329Sktlim@umich.edu 654329Sktlim@umich.edu /** Creates store set predictor with given table sizes. */ 662292SN/A StoreSet(uint64_t clear_period, int SSIT_size, int LFST_size); 672292SN/A 682292SN/A /** Default destructor. */ 692292SN/A ~StoreSet(); 7012109SRekai.GonzalezAlberquilla@arm.com 711060SN/A /** Initializes the store set predictor with the given table sizes. */ 7210172Sdam.sunwoo@arm.com void init(uint64_t clear_period, int SSIT_size, int LFST_size); 7310172Sdam.sunwoo@arm.com 7410172Sdam.sunwoo@arm.com /** Records a memory ordering violation between the younger load 7510172Sdam.sunwoo@arm.com * and the older store. */ 7610172Sdam.sunwoo@arm.com void violation(Addr store_PC, Addr load_PC); 772292SN/A 7810328Smitch.hayenga@arm.com /** Clears the store set predictor every so often so that all the 792292SN/A * entries aren't used and stores are constantly predicted as 802292SN/A * conflicting. 812292SN/A */ 822292SN/A void checkClear(); 832292SN/A 842292SN/A /** Inserts a load into the store set predictor. This does nothing but 852292SN/A * is included in case other predictors require a similar function. 861060SN/A */ 871060SN/A void insertLoad(Addr load_PC, InstSeqNum load_seq_num); 881061SN/A 891060SN/A /** Inserts a store into the store set predictor. Updates the 902292SN/A * LFST if the store has a valid SSID. */ 911062SN/A void insertStore(Addr store_PC, InstSeqNum store_seq_num, ThreadID tid); 921062SN/A 938240Snate@binkert.org /** Checks if the instruction with the given PC is dependent upon 941062SN/A * any store. @return Returns the sequence number of the store 951062SN/A * instruction this PC is dependent upon. Returns 0 if none. 961062SN/A */ 978240Snate@binkert.org InstSeqNum checkInst(Addr PC); 981062SN/A 991062SN/A /** Records this PC/sequence number as issued. */ 1001062SN/A void issued(Addr issued_PC, InstSeqNum issued_seq_num, bool is_store); 1018240Snate@binkert.org 1021062SN/A /** Squashes for a specific thread until the given sequence number. */ 1031062SN/A void squash(InstSeqNum squashed_num, ThreadID tid); 1042301SN/A 1058240Snate@binkert.org /** Resets all tables. */ 1062301SN/A void clear(); 1072301SN/A 1082292SN/A /** Debug function to dump the contents of the store list. */ 1098240Snate@binkert.org void dump(); 1102292SN/A 1112292SN/A private: 1121062SN/A /** Calculates the index into the SSIT based on the PC. */ 1138240Snate@binkert.org inline int calcIndex(Addr PC) 1141062SN/A { return (PC >> offsetBits) & indexMask; } 1151062SN/A 1161062SN/A /** Calculates a Store Set ID based on the PC. */ 1178240Snate@binkert.org inline SSID calcSSID(Addr PC) 1181062SN/A { return ((PC ^ (PC >> 10)) % LFSTSize); } 1191062SN/A 1201062SN/A /** The Store Set ID Table. */ 1218240Snate@binkert.org std::vector<SSID> SSIT; 1221062SN/A 1231062SN/A /** Bit vector to tell if the SSIT has a valid entry. */ 1241062SN/A std::vector<bool> validSSIT; 1258240Snate@binkert.org 1262292SN/A /** Last Fetched Store Table. */ 1271062SN/A std::vector<InstSeqNum> LFST; 1281062SN/A 1298240Snate@binkert.org /** Bit vector to tell if the LFST has a valid entry. */ 1302292SN/A std::vector<bool> validLFST; 1311062SN/A 13210239Sbinhpham@cs.rutgers.edu /** Map of stores that have been inserted into the store set, but 13310239Sbinhpham@cs.rutgers.edu * not yet issued or squashed. 13410239Sbinhpham@cs.rutgers.edu */ 13510239Sbinhpham@cs.rutgers.edu std::map<InstSeqNum, int, ltseqnum> storeList; 13610239Sbinhpham@cs.rutgers.edu 13710239Sbinhpham@cs.rutgers.edu typedef std::map<InstSeqNum, int, ltseqnum>::iterator SeqNumMapIt; 13810239Sbinhpham@cs.rutgers.edu 13910239Sbinhpham@cs.rutgers.edu /** Number of loads/stores to process before wiping predictor so all 1401062SN/A * entries don't get saturated 1418240Snate@binkert.org */ 1421062SN/A uint64_t clearPeriod; 1431062SN/A 1441062SN/A /** Store Set ID Table size, in entries. */ 1458240Snate@binkert.org int SSITSize; 1461062SN/A 1471062SN/A /** Last Fetched Store Table size, in entries. */ 1481062SN/A int LFSTSize; 1498240Snate@binkert.org 1501062SN/A /** Mask to obtain the index. */ 1511062SN/A int indexMask; 1521062SN/A 1538240Snate@binkert.org // HACK: Hardcoded for now. 1541062SN/A int offsetBits; 1551062SN/A 1561062SN/A /** Number of memory operations predicted since last clear of predictor */ 1578240Snate@binkert.org int memOpsPred; 1581062SN/A}; 1591062SN/A 1602301SN/A#endif // __CPU_O3_STORE_SET_HH__ 1618240Snate@binkert.org