11689SN/A/* 210330Smitch.hayenga@arm.com * Copyright (c) 2011, 2014 ARM Limited 38842Smrinmoy.ghosh@arm.com * All rights reserved 48842Smrinmoy.ghosh@arm.com * 58842Smrinmoy.ghosh@arm.com * The license below extends only to copyright in the software and shall 68842Smrinmoy.ghosh@arm.com * not be construed as granting a license to any other intellectual 78842Smrinmoy.ghosh@arm.com * property including but not limited to intellectual property relating 88842Smrinmoy.ghosh@arm.com * to a hardware implementation of the functionality of the software 98842Smrinmoy.ghosh@arm.com * licensed hereunder. You may use the software subject to the license 108842Smrinmoy.ghosh@arm.com * terms below provided that you ensure that this notice is replicated 118842Smrinmoy.ghosh@arm.com * unmodified and in its entirety in all distributions of the software, 128842Smrinmoy.ghosh@arm.com * modified or unmodified, in source code or in binary form. 138842Smrinmoy.ghosh@arm.com * 142345SN/A * Copyright (c) 2004-2006 The Regents of The University of Michigan 151689SN/A * All rights reserved. 161689SN/A * 171689SN/A * Redistribution and use in source and binary forms, with or without 181689SN/A * modification, are permitted provided that the following conditions are 191689SN/A * met: redistributions of source code must retain the above copyright 201689SN/A * notice, this list of conditions and the following disclaimer; 211689SN/A * redistributions in binary form must reproduce the above copyright 221689SN/A * notice, this list of conditions and the following disclaimer in the 231689SN/A * documentation and/or other materials provided with the distribution; 241689SN/A * neither the name of the copyright holders nor the names of its 251689SN/A * contributors may be used to endorse or promote products derived from 261689SN/A * this software without specific prior written permission. 271689SN/A * 281689SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 291689SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 301689SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 311689SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 321689SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 331689SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 341689SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 351689SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 361689SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 371689SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 381689SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392665SN/A * 402665SN/A * Authors: Kevin Lim 419480Snilay@cs.wisc.edu * Timothy M. Jones 429480Snilay@cs.wisc.edu * Nilay Vaish 431689SN/A */ 441689SN/A 459480Snilay@cs.wisc.edu#ifndef __CPU_PRED_TOURNAMENT_PRED_HH__ 469480Snilay@cs.wisc.edu#define __CPU_PRED_TOURNAMENT_PRED_HH__ 471062SN/A 486216SN/A#include <vector> 496216SN/A 5013960Sodanrc@yahoo.com.br#include "base/sat_counter.hh" 516216SN/A#include "base/types.hh" 529480Snilay@cs.wisc.edu#include "cpu/pred/bpred_unit.hh" 5310785Sgope@wisc.edu#include "params/TournamentBP.hh" 541062SN/A 552345SN/A/** 562345SN/A * Implements a tournament branch predictor, hopefully identical to the one 572345SN/A * used in the 21264. It has a local predictor, which uses a local history 582345SN/A * table to index into a table of counters, and a global predictor, which 592345SN/A * uses a global history to index into a table of counters. A choice 6011782Sarthur.perais@inria.fr * predictor chooses between the two. Both the global history register 6111782Sarthur.perais@inria.fr * and the selected local history are speculatively updated. 622345SN/A */ 639480Snilay@cs.wisc.educlass TournamentBP : public BPredUnit 641062SN/A{ 651062SN/A public: 661062SN/A /** 671062SN/A * Default branch predictor constructor. 681062SN/A */ 6910785Sgope@wisc.edu TournamentBP(const TournamentBPParams *params); 701062SN/A 711062SN/A /** 721062SN/A * Looks up the given address in the branch predictor and returns 732345SN/A * a true/false value as to whether it is taken. Also creates a 742345SN/A * BPHistory object to store any state it will need on squash/update. 751062SN/A * @param branch_addr The address of the branch to look up. 762345SN/A * @param bp_history Pointer that will be set to the BPHistory object. 771062SN/A * @return Whether or not the branch is taken. 781062SN/A */ 7911434Smitch.hayenga@arm.com bool lookup(ThreadID tid, Addr branch_addr, void * &bp_history); 802345SN/A 812345SN/A /** 822345SN/A * Records that there was an unconditional branch, and modifies 832345SN/A * the bp history to point to an object that has the previous 842345SN/A * global history stored in it. 852345SN/A * @param bp_history Pointer that will be set to the BPHistory object. 862345SN/A */ 8711434Smitch.hayenga@arm.com void uncondBranch(ThreadID tid, Addr pc, void * &bp_history); 888842Smrinmoy.ghosh@arm.com /** 898842Smrinmoy.ghosh@arm.com * Updates the branch predictor to Not Taken if a BTB entry is 908842Smrinmoy.ghosh@arm.com * invalid or not found. 918842Smrinmoy.ghosh@arm.com * @param branch_addr The address of the branch to look up. 928842Smrinmoy.ghosh@arm.com * @param bp_history Pointer to any bp history state. 938842Smrinmoy.ghosh@arm.com * @return Whether or not the branch is taken. 948842Smrinmoy.ghosh@arm.com */ 9511434Smitch.hayenga@arm.com void btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history); 961062SN/A /** 971062SN/A * Updates the branch predictor with the actual result of a branch. 981062SN/A * @param branch_addr The address of the branch to update. 991062SN/A * @param taken Whether or not the branch was taken. 1002345SN/A * @param bp_history Pointer to the BPHistory object that was created 1012345SN/A * when the branch was predicted. 1028842Smrinmoy.ghosh@arm.com * @param squashed is set when this function is called during a squash 1038842Smrinmoy.ghosh@arm.com * operation. 10413626Sjairo.balart@metempsy.com * @param inst Static instruction information 10513626Sjairo.balart@metempsy.com * @param corrTarget Resolved target of the branch (only needed if 10613626Sjairo.balart@metempsy.com * squashed) 1071062SN/A */ 10811434Smitch.hayenga@arm.com void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, 10913626Sjairo.balart@metempsy.com bool squashed, const StaticInstPtr & inst, Addr corrTarget); 1101062SN/A 1112345SN/A /** 1122345SN/A * Restores the global branch history on a squash. 1132345SN/A * @param bp_history Pointer to the BPHistory object that has the 1142345SN/A * previous global branch history in it. 1152345SN/A */ 11611434Smitch.hayenga@arm.com void squash(ThreadID tid, void *bp_history); 1172345SN/A 1181062SN/A private: 1192345SN/A /** 1202345SN/A * Returns if the branch should be taken or not, given a counter 1212345SN/A * value. 1222345SN/A * @param count The counter value. 1232345SN/A */ 1241062SN/A inline bool getPrediction(uint8_t &count); 1251062SN/A 1262345SN/A /** 1272345SN/A * Returns the local history index, given a branch address. 1282345SN/A * @param branch_addr The branch's PC address. 1292345SN/A */ 1301062SN/A inline unsigned calcLocHistIdx(Addr &branch_addr); 1311062SN/A 1322345SN/A /** Updates global history as taken. */ 13311434Smitch.hayenga@arm.com inline void updateGlobalHistTaken(ThreadID tid); 1341062SN/A 1352345SN/A /** Updates global history as not taken. */ 13611434Smitch.hayenga@arm.com inline void updateGlobalHistNotTaken(ThreadID tid); 1372345SN/A 1382345SN/A /** 1392345SN/A * Updates local histories as taken. 1402345SN/A * @param local_history_idx The local history table entry that 1412345SN/A * will be updated. 1422345SN/A */ 1432345SN/A inline void updateLocalHistTaken(unsigned local_history_idx); 1442345SN/A 1452345SN/A /** 1462345SN/A * Updates local histories as not taken. 1472345SN/A * @param local_history_idx The local history table entry that 1482345SN/A * will be updated. 1492345SN/A */ 1502345SN/A inline void updateLocalHistNotTaken(unsigned local_history_idx); 1512345SN/A 1522345SN/A /** 1532345SN/A * The branch history information that is created upon predicting 1542345SN/A * a branch. It will be passed back upon updating and squashing, 1552345SN/A * when the BP can use this information to update/restore its 1562345SN/A * state properly. 1572345SN/A */ 1582345SN/A struct BPHistory { 1592345SN/A#ifdef DEBUG 1602345SN/A BPHistory() 1612345SN/A { newCount++; } 1622345SN/A ~BPHistory() 1632345SN/A { newCount--; } 1642345SN/A 1652345SN/A static int newCount; 1662345SN/A#endif 1672345SN/A unsigned globalHistory; 16811098Slukefahr@umich.edu unsigned localHistoryIdx; 1698842Smrinmoy.ghosh@arm.com unsigned localHistory; 1702345SN/A bool localPredTaken; 1712345SN/A bool globalPredTaken; 1722345SN/A bool globalUsed; 1732345SN/A }; 1741062SN/A 1758842Smrinmoy.ghosh@arm.com /** Flag for invalid predictor index */ 1768842Smrinmoy.ghosh@arm.com static const int invalidPredictorIndex = -1; 1779360SE.Tomusk@sms.ed.ac.uk /** Number of counters in the local predictor. */ 1781684SN/A unsigned localPredictorSize; 1791062SN/A 1809360SE.Tomusk@sms.ed.ac.uk /** Mask to truncate values stored in the local history table. */ 1812356SN/A unsigned localPredictorMask; 1822356SN/A 1831062SN/A /** Number of bits of the local predictor's counters. */ 1841684SN/A unsigned localCtrBits; 1851062SN/A 18613959Sodanrc@yahoo.com.br /** Local counters. */ 18713959Sodanrc@yahoo.com.br std::vector<SatCounter> localCtrs; 18813959Sodanrc@yahoo.com.br 1891062SN/A /** Array of local history table entries. */ 1902292SN/A std::vector<unsigned> localHistoryTable; 1911062SN/A 1929360SE.Tomusk@sms.ed.ac.uk /** Number of entries in the local history table. */ 1931684SN/A unsigned localHistoryTableSize; 1941062SN/A 1959360SE.Tomusk@sms.ed.ac.uk /** Number of bits for each entry of the local history table. */ 1961684SN/A unsigned localHistoryBits; 1971062SN/A 1989360SE.Tomusk@sms.ed.ac.uk /** Number of entries in the global predictor. */ 1991684SN/A unsigned globalPredictorSize; 2001062SN/A 2011062SN/A /** Number of bits of the global predictor's counters. */ 2021684SN/A unsigned globalCtrBits; 2031062SN/A 20413959Sodanrc@yahoo.com.br /** Array of counters that make up the global predictor. */ 20513959Sodanrc@yahoo.com.br std::vector<SatCounter> globalCtrs; 20613959Sodanrc@yahoo.com.br 2079360SE.Tomusk@sms.ed.ac.uk /** Global history register. Contains as much history as specified by 2089360SE.Tomusk@sms.ed.ac.uk * globalHistoryBits. Actual number of bits used is determined by 2099360SE.Tomusk@sms.ed.ac.uk * globalHistoryMask and choiceHistoryMask. */ 21011434Smitch.hayenga@arm.com std::vector<unsigned> globalHistory; 2111062SN/A 2129360SE.Tomusk@sms.ed.ac.uk /** Number of bits for the global history. Determines maximum number of 2139360SE.Tomusk@sms.ed.ac.uk entries in global and choice predictor tables. */ 2141684SN/A unsigned globalHistoryBits; 2151062SN/A 2169360SE.Tomusk@sms.ed.ac.uk /** Mask to apply to globalHistory to access global history table. 2179360SE.Tomusk@sms.ed.ac.uk * Based on globalPredictorSize.*/ 2181062SN/A unsigned globalHistoryMask; 2191062SN/A 2209360SE.Tomusk@sms.ed.ac.uk /** Mask to apply to globalHistory to access choice history table. 2219360SE.Tomusk@sms.ed.ac.uk * Based on choicePredictorSize.*/ 2229360SE.Tomusk@sms.ed.ac.uk unsigned choiceHistoryMask; 2239360SE.Tomusk@sms.ed.ac.uk 2249360SE.Tomusk@sms.ed.ac.uk /** Mask to control how much history is stored. All of it might not be 2259360SE.Tomusk@sms.ed.ac.uk * used. */ 2269360SE.Tomusk@sms.ed.ac.uk unsigned historyRegisterMask; 2279360SE.Tomusk@sms.ed.ac.uk 2289360SE.Tomusk@sms.ed.ac.uk /** Number of entries in the choice predictor. */ 2291684SN/A unsigned choicePredictorSize; 2301062SN/A 2319360SE.Tomusk@sms.ed.ac.uk /** Number of bits in the choice predictor's counters. */ 2321684SN/A unsigned choiceCtrBits; 2331062SN/A 23413959Sodanrc@yahoo.com.br /** Array of counters that make up the choice predictor. */ 23513959Sodanrc@yahoo.com.br std::vector<SatCounter> choiceCtrs; 23613959Sodanrc@yahoo.com.br 2379360SE.Tomusk@sms.ed.ac.uk /** Thresholds for the counter value; above the threshold is taken, 2381062SN/A * equal to or below the threshold is not taken. 2391062SN/A */ 2409360SE.Tomusk@sms.ed.ac.uk unsigned localThreshold; 2419360SE.Tomusk@sms.ed.ac.uk unsigned globalThreshold; 2429360SE.Tomusk@sms.ed.ac.uk unsigned choiceThreshold; 2431062SN/A}; 2441062SN/A 2459480Snilay@cs.wisc.edu#endif // __CPU_PRED_TOURNAMENT_PRED_HH__ 246