tournament.hh revision 10330
12292SN/A/* 210031SAli.Saidi@ARM.com * Copyright (c) 2011, 2014 ARM Limited 39444SAndreas.Sandberg@ARM.com * All rights reserved 49444SAndreas.Sandberg@ARM.com * 59444SAndreas.Sandberg@ARM.com * The license below extends only to copyright in the software and shall 69444SAndreas.Sandberg@ARM.com * not be construed as granting a license to any other intellectual 79444SAndreas.Sandberg@ARM.com * property including but not limited to intellectual property relating 89444SAndreas.Sandberg@ARM.com * to a hardware implementation of the functionality of the software 99444SAndreas.Sandberg@ARM.com * licensed hereunder. You may use the software subject to the license 109444SAndreas.Sandberg@ARM.com * terms below provided that you ensure that this notice is replicated 119444SAndreas.Sandberg@ARM.com * unmodified and in its entirety in all distributions of the software, 129444SAndreas.Sandberg@ARM.com * modified or unmodified, in source code or in binary form. 139444SAndreas.Sandberg@ARM.com * 142329SN/A * Copyright (c) 2004-2006 The Regents of The University of Michigan 1510239Sbinhpham@cs.rutgers.edu * All rights reserved. 162292SN/A * 172292SN/A * Redistribution and use in source and binary forms, with or without 182292SN/A * modification, are permitted provided that the following conditions are 192292SN/A * met: redistributions of source code must retain the above copyright 202292SN/A * notice, this list of conditions and the following disclaimer; 212292SN/A * redistributions in binary form must reproduce the above copyright 222292SN/A * notice, this list of conditions and the following disclaimer in the 232292SN/A * documentation and/or other materials provided with the distribution; 242292SN/A * neither the name of the copyright holders nor the names of its 252292SN/A * contributors may be used to endorse or promote products derived from 262292SN/A * this software without specific prior written permission. 272292SN/A * 282292SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292292SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302292SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312292SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 322292SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 332292SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342292SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352292SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362292SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372292SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382292SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 392292SN/A * 402689Sktlim@umich.edu * Authors: Kevin Lim 412689Sktlim@umich.edu * Timothy M. Jones 422689Sktlim@umich.edu * Nilay Vaish 432292SN/A */ 442292SN/A 452292SN/A#ifndef __CPU_PRED_TOURNAMENT_PRED_HH__ 462292SN/A#define __CPU_PRED_TOURNAMENT_PRED_HH__ 472292SN/A 482329SN/A#include <vector> 494395Ssaidi@eecs.umich.edu 502292SN/A#include "base/types.hh" 512292SN/A#include "cpu/pred/bpred_unit.hh" 522292SN/A#include "cpu/pred/sat_counter.hh" 538591Sgblack@eecs.umich.edu 548506Sgblack@eecs.umich.edu/** 553326Sktlim@umich.edu * Implements a tournament branch predictor, hopefully identical to the one 568481Sgblack@eecs.umich.edu * used in the 21264. It has a local predictor, which uses a local history 578229Snate@binkert.org * table to index into a table of counters, and a global predictor, which 586658Snate@binkert.org * uses a global history to index into a table of counters. A choice 592292SN/A * predictor chooses between the two. Only the global history register 608230Snate@binkert.org * is speculatively updated, the rest are updated upon branches committing 618232Snate@binkert.org * or misspeculating. 623348Sbinkertn@umich.edu */ 632669Sktlim@umich.educlass TournamentBP : public BPredUnit 648817Sgblack@eecs.umich.edu{ 652292SN/A public: 668737Skoansin.tan@gmail.com /** 675529Snate@binkert.org * Default branch predictor constructor. 682292SN/A */ 692329SN/A TournamentBP(const Params *params); 702329SN/A 712329SN/A /** 722329SN/A * Looks up the given address in the branch predictor and returns 732329SN/A * a true/false value as to whether it is taken. Also creates a 742329SN/A * BPHistory object to store any state it will need on squash/update. 752329SN/A * @param branch_addr The address of the branch to look up. 762329SN/A * @param bp_history Pointer that will be set to the BPHistory object. 772329SN/A * @return Whether or not the branch is taken. 782329SN/A */ 792292SN/A bool lookup(Addr branch_addr, void * &bp_history); 802292SN/A 812292SN/A /** 822292SN/A * Records that there was an unconditional branch, and modifies 832733Sktlim@umich.edu * the bp history to point to an object that has the previous 842292SN/A * global history stored in it. 852292SN/A * @param bp_history Pointer that will be set to the BPHistory object. 862907Sktlim@umich.edu */ 872292SN/A void uncondBranch(void * &bp_history); 882292SN/A /** 892292SN/A * Updates the branch predictor to Not Taken if a BTB entry is 902292SN/A * invalid or not found. 912292SN/A * @param branch_addr The address of the branch to look up. 922292SN/A * @param bp_history Pointer to any bp history state. 932292SN/A * @return Whether or not the branch is taken. 945529Snate@binkert.org */ 955529Snate@binkert.org void btbUpdate(Addr branch_addr, void * &bp_history); 965529Snate@binkert.org /** 972292SN/A * Updates the branch predictor with the actual result of a branch. 982292SN/A * @param branch_addr The address of the branch to update. 992292SN/A * @param taken Whether or not the branch was taken. 1002292SN/A * @param bp_history Pointer to the BPHistory object that was created 1012727Sktlim@umich.edu * when the branch was predicted. 1022727Sktlim@umich.edu * @param squashed is set when this function is called during a squash 1032727Sktlim@umich.edu * operation. 1042907Sktlim@umich.edu */ 1058922Swilliam.wang@arm.com void update(Addr branch_addr, bool taken, void *bp_history, bool squashed); 1062907Sktlim@umich.edu 1079444SAndreas.Sandberg@ARM.com void retireSquashed(void *bp_history); 1089444SAndreas.Sandberg@ARM.com 1092307SN/A /** 1102348SN/A * Restores the global branch history on a squash. 1112307SN/A * @param bp_history Pointer to the BPHistory object that has the 1122307SN/A * previous global branch history in it. 1132292SN/A */ 1142292SN/A void squash(void *bp_history); 1152292SN/A 1162292SN/A /** Returns the global history. */ 1172292SN/A inline unsigned readGlobalHist() { return globalHistory; } 1182292SN/A 1192292SN/A private: 1202292SN/A /** 1212292SN/A * Returns if the branch should be taken or not, given a counter 1222292SN/A * value. 1232292SN/A * @param count The counter value. 1242292SN/A */ 1252292SN/A inline bool getPrediction(uint8_t &count); 1262292SN/A 1278545Ssaidi@eecs.umich.edu /** 1288545Ssaidi@eecs.umich.edu * Returns the local history index, given a branch address. 1298545Ssaidi@eecs.umich.edu * @param branch_addr The branch's PC address. 1308199SAli.Saidi@ARM.com */ 1318199SAli.Saidi@ARM.com inline unsigned calcLocHistIdx(Addr &branch_addr); 1328199SAli.Saidi@ARM.com 1338199SAli.Saidi@ARM.com /** Updates global history as taken. */ 1348199SAli.Saidi@ARM.com inline void updateGlobalHistTaken(); 1358545Ssaidi@eecs.umich.edu 1368545Ssaidi@eecs.umich.edu /** Updates global history as not taken. */ 1378545Ssaidi@eecs.umich.edu inline void updateGlobalHistNotTaken(); 1388545Ssaidi@eecs.umich.edu 1398545Ssaidi@eecs.umich.edu /** 1408545Ssaidi@eecs.umich.edu * Updates local histories as taken. 1412292SN/A * @param local_history_idx The local history table entry that 1422292SN/A * will be updated. 1432292SN/A */ 1442329SN/A inline void updateLocalHistTaken(unsigned local_history_idx); 1452292SN/A 1462292SN/A /** 1472292SN/A * Updates local histories as not taken. 1482292SN/A * @param local_history_idx The local history table entry that 1492292SN/A * will be updated. 1502292SN/A */ 1512292SN/A inline void updateLocalHistNotTaken(unsigned local_history_idx); 1522292SN/A 1532292SN/A /** 1542292SN/A * The branch history information that is created upon predicting 1552292SN/A * a branch. It will be passed back upon updating and squashing, 1562292SN/A * when the BP can use this information to update/restore its 1572292SN/A * state properly. 1582292SN/A */ 1592790Sktlim@umich.edu struct BPHistory { 1602790Sktlim@umich.edu#ifdef DEBUG 1612669Sktlim@umich.edu BPHistory() 1622669Sktlim@umich.edu { newCount++; } 1632292SN/A ~BPHistory() 1642292SN/A { newCount--; } 1652292SN/A 1662292SN/A static int newCount; 1672292SN/A#endif 1682292SN/A unsigned globalHistory; 1692292SN/A unsigned localHistory; 1702292SN/A bool localPredTaken; 1712292SN/A bool globalPredTaken; 1722292SN/A bool globalUsed; 1732292SN/A }; 1742292SN/A 1752292SN/A /** Flag for invalid predictor index */ 1762292SN/A static const int invalidPredictorIndex = -1; 1772292SN/A /** Local counters. */ 1782292SN/A std::vector<SatCounter> localCtrs; 1792292SN/A 1802292SN/A /** Number of counters in the local predictor. */ 1812292SN/A unsigned localPredictorSize; 1822292SN/A 1832292SN/A /** Mask to truncate values stored in the local history table. */ 1842292SN/A unsigned localPredictorMask; 1852292SN/A 1862329SN/A /** Number of bits of the local predictor's counters. */ 1872292SN/A unsigned localCtrBits; 1882292SN/A 1892292SN/A /** Array of local history table entries. */ 1902348SN/A std::vector<unsigned> localHistoryTable; 1912292SN/A 1922292SN/A /** Number of entries in the local history table. */ 1932292SN/A unsigned localHistoryTableSize; 1942348SN/A 1952292SN/A /** Number of bits for each entry of the local history table. */ 1962292SN/A unsigned localHistoryBits; 1972292SN/A 1982348SN/A /** Array of counters that make up the global predictor. */ 1992292SN/A std::vector<SatCounter> globalCtrs; 2002292SN/A 2012292SN/A /** Number of entries in the global predictor. */ 20210239Sbinhpham@cs.rutgers.edu unsigned globalPredictorSize; 20310239Sbinhpham@cs.rutgers.edu 20410239Sbinhpham@cs.rutgers.edu /** Number of bits of the global predictor's counters. */ 20510239Sbinhpham@cs.rutgers.edu unsigned globalCtrBits; 20610239Sbinhpham@cs.rutgers.edu 2072292SN/A /** Global history register. Contains as much history as specified by 2082292SN/A * globalHistoryBits. Actual number of bits used is determined by 2092292SN/A * globalHistoryMask and choiceHistoryMask. */ 2102292SN/A unsigned globalHistory; 2112292SN/A 2122292SN/A /** Number of bits for the global history. Determines maximum number of 2132292SN/A entries in global and choice predictor tables. */ 2142292SN/A unsigned globalHistoryBits; 2152292SN/A 2162292SN/A /** Mask to apply to globalHistory to access global history table. 2179444SAndreas.Sandberg@ARM.com * Based on globalPredictorSize.*/ 2189444SAndreas.Sandberg@ARM.com unsigned globalHistoryMask; 2199444SAndreas.Sandberg@ARM.com 2202292SN/A /** Mask to apply to globalHistory to access choice history table. 2212292SN/A * Based on choicePredictorSize.*/ 2222292SN/A unsigned choiceHistoryMask; 2232292SN/A 2242292SN/A /** Mask to control how much history is stored. All of it might not be 2252292SN/A * used. */ 2269444SAndreas.Sandberg@ARM.com unsigned historyRegisterMask; 2279444SAndreas.Sandberg@ARM.com 2289444SAndreas.Sandberg@ARM.com /** Array of counters that make up the choice predictor. */ 2299444SAndreas.Sandberg@ARM.com std::vector<SatCounter> choiceCtrs; 2309444SAndreas.Sandberg@ARM.com 2319444SAndreas.Sandberg@ARM.com /** Number of entries in the choice predictor. */ 2322292SN/A unsigned choicePredictorSize; 2332292SN/A 2342292SN/A /** Number of bits in the choice predictor's counters. */ 2352292SN/A unsigned choiceCtrBits; 2362292SN/A 2372292SN/A /** Number of bits to shift the instruction over to get rid of the word 2382292SN/A * offset. 2392292SN/A */ 2402292SN/A unsigned instShiftAmt; 2412292SN/A 2422292SN/A /** Thresholds for the counter value; above the threshold is taken, 2432678Sktlim@umich.edu * equal to or below the threshold is not taken. 2442678Sktlim@umich.edu */ 2452292SN/A unsigned localThreshold; 2462907Sktlim@umich.edu unsigned globalThreshold; 2472907Sktlim@umich.edu unsigned choiceThreshold; 2482907Sktlim@umich.edu}; 2492292SN/A 2509444SAndreas.Sandberg@ARM.com#endif // __CPU_PRED_TOURNAMENT_PRED_HH__ 2519444SAndreas.Sandberg@ARM.com