tournament.hh revision 8842
11689SN/A/* 28842Smrinmoy.ghosh@arm.com * Copyright (c) 2011 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 411689SN/A */ 421689SN/A 432292SN/A#ifndef __CPU_O3_TOURNAMENT_PRED_HH__ 442292SN/A#define __CPU_O3_TOURNAMENT_PRED_HH__ 451062SN/A 466216SN/A#include <vector> 476216SN/A 486216SN/A#include "base/types.hh" 491717SN/A#include "cpu/o3/sat_counter.hh" 501062SN/A 512345SN/A/** 522345SN/A * Implements a tournament branch predictor, hopefully identical to the one 532345SN/A * used in the 21264. It has a local predictor, which uses a local history 542345SN/A * table to index into a table of counters, and a global predictor, which 552345SN/A * uses a global history to index into a table of counters. A choice 562345SN/A * predictor chooses between the two. Only the global history register 572345SN/A * is speculatively updated, the rest are updated upon branches committing 582345SN/A * or misspeculating. 592345SN/A */ 601062SN/Aclass TournamentBP 611062SN/A{ 621062SN/A public: 631062SN/A /** 641062SN/A * Default branch predictor constructor. 651062SN/A */ 662292SN/A TournamentBP(unsigned localPredictorSize, 672292SN/A unsigned localCtrBits, 682292SN/A unsigned localHistoryTableSize, 692292SN/A unsigned localHistoryBits, 702292SN/A unsigned globalPredictorSize, 712292SN/A unsigned globalHistoryBits, 722292SN/A unsigned globalCtrBits, 732292SN/A unsigned choicePredictorSize, 742292SN/A unsigned choiceCtrBits, 751062SN/A unsigned instShiftAmt); 761062SN/A 771062SN/A /** 781062SN/A * Looks up the given address in the branch predictor and returns 792345SN/A * a true/false value as to whether it is taken. Also creates a 802345SN/A * BPHistory object to store any state it will need on squash/update. 811062SN/A * @param branch_addr The address of the branch to look up. 822345SN/A * @param bp_history Pointer that will be set to the BPHistory object. 831062SN/A * @return Whether or not the branch is taken. 841062SN/A */ 852345SN/A bool lookup(Addr &branch_addr, void * &bp_history); 862345SN/A 872345SN/A /** 882345SN/A * Records that there was an unconditional branch, and modifies 892345SN/A * the bp history to point to an object that has the previous 902345SN/A * global history stored in it. 912345SN/A * @param bp_history Pointer that will be set to the BPHistory object. 922345SN/A */ 932345SN/A void uncondBr(void * &bp_history); 948842Smrinmoy.ghosh@arm.com /** 958842Smrinmoy.ghosh@arm.com * Updates the branch predictor to Not Taken if a BTB entry is 968842Smrinmoy.ghosh@arm.com * invalid or not found. 978842Smrinmoy.ghosh@arm.com * @param branch_addr The address of the branch to look up. 988842Smrinmoy.ghosh@arm.com * @param bp_history Pointer to any bp history state. 998842Smrinmoy.ghosh@arm.com * @return Whether or not the branch is taken. 1008842Smrinmoy.ghosh@arm.com */ 1018842Smrinmoy.ghosh@arm.com void BTBUpdate(Addr &branch_addr, void * &bp_history); 1021062SN/A /** 1031062SN/A * Updates the branch predictor with the actual result of a branch. 1041062SN/A * @param branch_addr The address of the branch to update. 1051062SN/A * @param taken Whether or not the branch was taken. 1062345SN/A * @param bp_history Pointer to the BPHistory object that was created 1072345SN/A * when the branch was predicted. 1088842Smrinmoy.ghosh@arm.com * @param squashed is set when this function is called during a squash 1098842Smrinmoy.ghosh@arm.com * operation. 1101062SN/A */ 1118842Smrinmoy.ghosh@arm.com void update(Addr &branch_addr, bool taken, void *bp_history, bool squashed); 1121062SN/A 1132345SN/A /** 1142345SN/A * Restores the global branch history on a squash. 1152345SN/A * @param bp_history Pointer to the BPHistory object that has the 1162345SN/A * previous global branch history in it. 1172345SN/A */ 1182345SN/A void squash(void *bp_history); 1192345SN/A 1202345SN/A /** Returns the global history. */ 1211684SN/A inline unsigned readGlobalHist() { return globalHistory; } 1221062SN/A 1231062SN/A private: 1242345SN/A /** 1252345SN/A * Returns if the branch should be taken or not, given a counter 1262345SN/A * value. 1272345SN/A * @param count The counter value. 1282345SN/A */ 1291062SN/A inline bool getPrediction(uint8_t &count); 1301062SN/A 1312345SN/A /** 1322345SN/A * Returns the local history index, given a branch address. 1332345SN/A * @param branch_addr The branch's PC address. 1342345SN/A */ 1351062SN/A inline unsigned calcLocHistIdx(Addr &branch_addr); 1361062SN/A 1372345SN/A /** Updates global history as taken. */ 1382345SN/A inline void updateGlobalHistTaken(); 1391062SN/A 1402345SN/A /** Updates global history as not taken. */ 1412345SN/A inline void updateGlobalHistNotTaken(); 1422345SN/A 1432345SN/A /** 1442345SN/A * Updates local histories as taken. 1452345SN/A * @param local_history_idx The local history table entry that 1462345SN/A * will be updated. 1472345SN/A */ 1482345SN/A inline void updateLocalHistTaken(unsigned local_history_idx); 1492345SN/A 1502345SN/A /** 1512345SN/A * Updates local histories as not taken. 1522345SN/A * @param local_history_idx The local history table entry that 1532345SN/A * will be updated. 1542345SN/A */ 1552345SN/A inline void updateLocalHistNotTaken(unsigned local_history_idx); 1562345SN/A 1572345SN/A /** 1582345SN/A * The branch history information that is created upon predicting 1592345SN/A * a branch. It will be passed back upon updating and squashing, 1602345SN/A * when the BP can use this information to update/restore its 1612345SN/A * state properly. 1622345SN/A */ 1632345SN/A struct BPHistory { 1642345SN/A#ifdef DEBUG 1652345SN/A BPHistory() 1662345SN/A { newCount++; } 1672345SN/A ~BPHistory() 1682345SN/A { newCount--; } 1692345SN/A 1702345SN/A static int newCount; 1712345SN/A#endif 1722345SN/A unsigned globalHistory; 1738842Smrinmoy.ghosh@arm.com unsigned localHistory; 1742345SN/A bool localPredTaken; 1752345SN/A bool globalPredTaken; 1762345SN/A bool globalUsed; 1772345SN/A }; 1781062SN/A 1798842Smrinmoy.ghosh@arm.com /** Flag for invalid predictor index */ 1808842Smrinmoy.ghosh@arm.com static const int invalidPredictorIndex = -1; 1811062SN/A /** Local counters. */ 1822292SN/A std::vector<SatCounter> localCtrs; 1831062SN/A 1841062SN/A /** Size of the local predictor. */ 1851684SN/A unsigned localPredictorSize; 1861062SN/A 1872356SN/A /** Mask to get the proper index bits into the predictor. */ 1882356SN/A unsigned localPredictorMask; 1892356SN/A 1901062SN/A /** Number of bits of the local predictor's counters. */ 1911684SN/A unsigned localCtrBits; 1921062SN/A 1931062SN/A /** Array of local history table entries. */ 1942292SN/A std::vector<unsigned> localHistoryTable; 1951062SN/A 1961062SN/A /** Size of the local history table. */ 1971684SN/A unsigned localHistoryTableSize; 1981062SN/A 1991062SN/A /** Number of bits for each entry of the local history table. 2001062SN/A * @todo Doesn't this come from the size of the local predictor? 2011062SN/A */ 2021684SN/A unsigned localHistoryBits; 2031062SN/A 2041062SN/A /** Mask to get the proper local history. */ 2051062SN/A unsigned localHistoryMask; 2061062SN/A 2071062SN/A /** Array of counters that make up the global predictor. */ 2082292SN/A std::vector<SatCounter> globalCtrs; 2091062SN/A 2101062SN/A /** Size of the global predictor. */ 2111684SN/A unsigned globalPredictorSize; 2121062SN/A 2131062SN/A /** Number of bits of the global predictor's counters. */ 2141684SN/A unsigned globalCtrBits; 2151062SN/A 2161062SN/A /** Global history register. */ 2171684SN/A unsigned globalHistory; 2181062SN/A 2191062SN/A /** Number of bits for the global history. */ 2201684SN/A unsigned globalHistoryBits; 2211062SN/A 2221062SN/A /** Mask to get the proper global history. */ 2231062SN/A unsigned globalHistoryMask; 2241062SN/A 2251062SN/A /** Array of counters that make up the choice predictor. */ 2262292SN/A std::vector<SatCounter> choiceCtrs; 2271062SN/A 2281062SN/A /** Size of the choice predictor (identical to the global predictor). */ 2291684SN/A unsigned choicePredictorSize; 2301062SN/A 2311062SN/A /** Number of bits of the choice predictor's counters. */ 2321684SN/A unsigned choiceCtrBits; 2331062SN/A 2341062SN/A /** Number of bits to shift the instruction over to get rid of the word 2351062SN/A * offset. 2361062SN/A */ 2371062SN/A unsigned instShiftAmt; 2381062SN/A 2391062SN/A /** Threshold for the counter value; above the threshold is taken, 2401062SN/A * equal to or below the threshold is not taken. 2411062SN/A */ 2421062SN/A unsigned threshold; 2431062SN/A}; 2441062SN/A 2452292SN/A#endif // __CPU_O3_TOURNAMENT_PRED_HH__ 246