tournament.hh revision 11782
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 506216SN/A#include "base/types.hh" 519480Snilay@cs.wisc.edu#include "cpu/pred/bpred_unit.hh" 529480Snilay@cs.wisc.edu#include "cpu/pred/sat_counter.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. 1041062SN/A */ 10511434Smitch.hayenga@arm.com void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, 10611434Smitch.hayenga@arm.com bool squashed); 1071062SN/A 10811434Smitch.hayenga@arm.com void retireSquashed(ThreadID tid, void *bp_history); 10910330Smitch.hayenga@arm.com 1102345SN/A /** 1112345SN/A * Restores the global branch history on a squash. 1122345SN/A * @param bp_history Pointer to the BPHistory object that has the 1132345SN/A * previous global branch history in it. 1142345SN/A */ 11511434Smitch.hayenga@arm.com void squash(ThreadID tid, void *bp_history); 1162345SN/A 11711434Smitch.hayenga@arm.com unsigned getGHR(ThreadID tid, void *bp_history) const; 1181062SN/A 1191062SN/A private: 1202345SN/A /** 1212345SN/A * Returns if the branch should be taken or not, given a counter 1222345SN/A * value. 1232345SN/A * @param count The counter value. 1242345SN/A */ 1251062SN/A inline bool getPrediction(uint8_t &count); 1261062SN/A 1272345SN/A /** 1282345SN/A * Returns the local history index, given a branch address. 1292345SN/A * @param branch_addr The branch's PC address. 1302345SN/A */ 1311062SN/A inline unsigned calcLocHistIdx(Addr &branch_addr); 1321062SN/A 1332345SN/A /** Updates global history as taken. */ 13411434Smitch.hayenga@arm.com inline void updateGlobalHistTaken(ThreadID tid); 1351062SN/A 1362345SN/A /** Updates global history as not taken. */ 13711434Smitch.hayenga@arm.com inline void updateGlobalHistNotTaken(ThreadID tid); 1382345SN/A 1392345SN/A /** 1402345SN/A * Updates local histories as taken. 1412345SN/A * @param local_history_idx The local history table entry that 1422345SN/A * will be updated. 1432345SN/A */ 1442345SN/A inline void updateLocalHistTaken(unsigned local_history_idx); 1452345SN/A 1462345SN/A /** 1472345SN/A * Updates local histories as not taken. 1482345SN/A * @param local_history_idx The local history table entry that 1492345SN/A * will be updated. 1502345SN/A */ 1512345SN/A inline void updateLocalHistNotTaken(unsigned local_history_idx); 1522345SN/A 1532345SN/A /** 1542345SN/A * The branch history information that is created upon predicting 1552345SN/A * a branch. It will be passed back upon updating and squashing, 1562345SN/A * when the BP can use this information to update/restore its 1572345SN/A * state properly. 1582345SN/A */ 1592345SN/A struct BPHistory { 1602345SN/A#ifdef DEBUG 1612345SN/A BPHistory() 1622345SN/A { newCount++; } 1632345SN/A ~BPHistory() 1642345SN/A { newCount--; } 1652345SN/A 1662345SN/A static int newCount; 1672345SN/A#endif 1682345SN/A unsigned globalHistory; 16911098Slukefahr@umich.edu unsigned localHistoryIdx; 1708842Smrinmoy.ghosh@arm.com unsigned localHistory; 1712345SN/A bool localPredTaken; 1722345SN/A bool globalPredTaken; 1732345SN/A bool globalUsed; 1742345SN/A }; 1751062SN/A 1768842Smrinmoy.ghosh@arm.com /** Flag for invalid predictor index */ 1778842Smrinmoy.ghosh@arm.com static const int invalidPredictorIndex = -1; 1781062SN/A /** Local counters. */ 1792292SN/A std::vector<SatCounter> localCtrs; 1801062SN/A 1819360SE.Tomusk@sms.ed.ac.uk /** Number of counters in the local predictor. */ 1821684SN/A unsigned localPredictorSize; 1831062SN/A 1849360SE.Tomusk@sms.ed.ac.uk /** Mask to truncate values stored in the local history table. */ 1852356SN/A unsigned localPredictorMask; 1862356SN/A 1871062SN/A /** Number of bits of the local predictor's counters. */ 1881684SN/A unsigned localCtrBits; 1891062SN/A 1901062SN/A /** Array of local history table entries. */ 1912292SN/A std::vector<unsigned> localHistoryTable; 1921062SN/A 1939360SE.Tomusk@sms.ed.ac.uk /** Number of entries in the local history table. */ 1941684SN/A unsigned localHistoryTableSize; 1951062SN/A 1969360SE.Tomusk@sms.ed.ac.uk /** Number of bits for each entry of the local history table. */ 1971684SN/A unsigned localHistoryBits; 1981062SN/A 1991062SN/A /** Array of counters that make up the global predictor. */ 2002292SN/A std::vector<SatCounter> globalCtrs; 2011062SN/A 2029360SE.Tomusk@sms.ed.ac.uk /** Number of entries in the global predictor. */ 2031684SN/A unsigned globalPredictorSize; 2041062SN/A 2051062SN/A /** Number of bits of the global predictor's counters. */ 2061684SN/A unsigned globalCtrBits; 2071062SN/A 2089360SE.Tomusk@sms.ed.ac.uk /** Global history register. Contains as much history as specified by 2099360SE.Tomusk@sms.ed.ac.uk * globalHistoryBits. Actual number of bits used is determined by 2109360SE.Tomusk@sms.ed.ac.uk * globalHistoryMask and choiceHistoryMask. */ 21111434Smitch.hayenga@arm.com std::vector<unsigned> globalHistory; 2121062SN/A 2139360SE.Tomusk@sms.ed.ac.uk /** Number of bits for the global history. Determines maximum number of 2149360SE.Tomusk@sms.ed.ac.uk entries in global and choice predictor tables. */ 2151684SN/A unsigned globalHistoryBits; 2161062SN/A 2179360SE.Tomusk@sms.ed.ac.uk /** Mask to apply to globalHistory to access global history table. 2189360SE.Tomusk@sms.ed.ac.uk * Based on globalPredictorSize.*/ 2191062SN/A unsigned globalHistoryMask; 2201062SN/A 2219360SE.Tomusk@sms.ed.ac.uk /** Mask to apply to globalHistory to access choice history table. 2229360SE.Tomusk@sms.ed.ac.uk * Based on choicePredictorSize.*/ 2239360SE.Tomusk@sms.ed.ac.uk unsigned choiceHistoryMask; 2249360SE.Tomusk@sms.ed.ac.uk 2259360SE.Tomusk@sms.ed.ac.uk /** Mask to control how much history is stored. All of it might not be 2269360SE.Tomusk@sms.ed.ac.uk * used. */ 2279360SE.Tomusk@sms.ed.ac.uk unsigned historyRegisterMask; 2289360SE.Tomusk@sms.ed.ac.uk 2291062SN/A /** Array of counters that make up the choice predictor. */ 2302292SN/A std::vector<SatCounter> choiceCtrs; 2311062SN/A 2329360SE.Tomusk@sms.ed.ac.uk /** Number of entries in the choice predictor. */ 2331684SN/A unsigned choicePredictorSize; 2341062SN/A 2359360SE.Tomusk@sms.ed.ac.uk /** Number of bits in the choice predictor's counters. */ 2361684SN/A unsigned choiceCtrBits; 2371062SN/A 2389360SE.Tomusk@sms.ed.ac.uk /** Thresholds for the counter value; above the threshold is taken, 2391062SN/A * equal to or below the threshold is not taken. 2401062SN/A */ 2419360SE.Tomusk@sms.ed.ac.uk unsigned localThreshold; 2429360SE.Tomusk@sms.ed.ac.uk unsigned globalThreshold; 2439360SE.Tomusk@sms.ed.ac.uk unsigned choiceThreshold; 2441062SN/A}; 2451062SN/A 2469480Snilay@cs.wisc.edu#endif // __CPU_PRED_TOURNAMENT_PRED_HH__ 247