tournament.hh revision 2356
110396Sakash.bagdia@arm.com/* 210396Sakash.bagdia@arm.com * Copyright (c) 2004-2006 The Regents of The University of Michigan 310396Sakash.bagdia@arm.com * All rights reserved. 410396Sakash.bagdia@arm.com * 510396Sakash.bagdia@arm.com * Redistribution and use in source and binary forms, with or without 610396Sakash.bagdia@arm.com * modification, are permitted provided that the following conditions are 710396Sakash.bagdia@arm.com * met: redistributions of source code must retain the above copyright 810396Sakash.bagdia@arm.com * notice, this list of conditions and the following disclaimer; 910396Sakash.bagdia@arm.com * redistributions in binary form must reproduce the above copyright 1010396Sakash.bagdia@arm.com * notice, this list of conditions and the following disclaimer in the 1110396Sakash.bagdia@arm.com * documentation and/or other materials provided with the distribution; 1210396Sakash.bagdia@arm.com * neither the name of the copyright holders nor the names of its 1310396Sakash.bagdia@arm.com * contributors may be used to endorse or promote products derived from 1410396Sakash.bagdia@arm.com * this software without specific prior written permission. 1510396Sakash.bagdia@arm.com * 1610396Sakash.bagdia@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1710396Sakash.bagdia@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1810396Sakash.bagdia@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1910396Sakash.bagdia@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2010396Sakash.bagdia@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2110396Sakash.bagdia@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2210396Sakash.bagdia@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2310396Sakash.bagdia@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2410396Sakash.bagdia@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2510396Sakash.bagdia@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2610396Sakash.bagdia@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2710396Sakash.bagdia@arm.com */ 2810396Sakash.bagdia@arm.com 2910396Sakash.bagdia@arm.com#ifndef __CPU_O3_TOURNAMENT_PRED_HH__ 3010396Sakash.bagdia@arm.com#define __CPU_O3_TOURNAMENT_PRED_HH__ 3110396Sakash.bagdia@arm.com 3210396Sakash.bagdia@arm.com// For Addr type. 3310396Sakash.bagdia@arm.com#include "arch/isa_traits.hh" 3410396Sakash.bagdia@arm.com#include "cpu/o3/sat_counter.hh" 3510396Sakash.bagdia@arm.com#include <vector> 3610396Sakash.bagdia@arm.com 3710396Sakash.bagdia@arm.com/** 3810396Sakash.bagdia@arm.com * Implements a tournament branch predictor, hopefully identical to the one 3910396Sakash.bagdia@arm.com * used in the 21264. It has a local predictor, which uses a local history 4010396Sakash.bagdia@arm.com * table to index into a table of counters, and a global predictor, which 4110396Sakash.bagdia@arm.com * uses a global history to index into a table of counters. A choice 4210396Sakash.bagdia@arm.com * predictor chooses between the two. Only the global history register 4310396Sakash.bagdia@arm.com * is speculatively updated, the rest are updated upon branches committing 4410396Sakash.bagdia@arm.com * or misspeculating. 4510396Sakash.bagdia@arm.com */ 4610396Sakash.bagdia@arm.comclass TournamentBP 4710396Sakash.bagdia@arm.com{ 4810396Sakash.bagdia@arm.com public: 4910396Sakash.bagdia@arm.com /** 5010396Sakash.bagdia@arm.com * Default branch predictor constructor. 5110396Sakash.bagdia@arm.com */ 5210396Sakash.bagdia@arm.com TournamentBP(unsigned localPredictorSize, 5310396Sakash.bagdia@arm.com unsigned localCtrBits, 5410396Sakash.bagdia@arm.com unsigned localHistoryTableSize, 5510396Sakash.bagdia@arm.com unsigned localHistoryBits, 5610396Sakash.bagdia@arm.com unsigned globalPredictorSize, 5710396Sakash.bagdia@arm.com unsigned globalHistoryBits, 5810396Sakash.bagdia@arm.com unsigned globalCtrBits, 5910396Sakash.bagdia@arm.com unsigned choicePredictorSize, 6010396Sakash.bagdia@arm.com unsigned choiceCtrBits, 6110396Sakash.bagdia@arm.com unsigned instShiftAmt); 6210396Sakash.bagdia@arm.com 6310396Sakash.bagdia@arm.com /** 6410396Sakash.bagdia@arm.com * Looks up the given address in the branch predictor and returns 6510396Sakash.bagdia@arm.com * a true/false value as to whether it is taken. Also creates a 6610396Sakash.bagdia@arm.com * BPHistory object to store any state it will need on squash/update. 6710396Sakash.bagdia@arm.com * @param branch_addr The address of the branch to look up. 6810396Sakash.bagdia@arm.com * @param bp_history Pointer that will be set to the BPHistory object. 6910396Sakash.bagdia@arm.com * @return Whether or not the branch is taken. 7010396Sakash.bagdia@arm.com */ 7110396Sakash.bagdia@arm.com bool lookup(Addr &branch_addr, void * &bp_history); 7210396Sakash.bagdia@arm.com 7310396Sakash.bagdia@arm.com /** 7410396Sakash.bagdia@arm.com * Records that there was an unconditional branch, and modifies 7510396Sakash.bagdia@arm.com * the bp history to point to an object that has the previous 7610396Sakash.bagdia@arm.com * global history stored in it. 7710396Sakash.bagdia@arm.com * @param bp_history Pointer that will be set to the BPHistory object. 7810396Sakash.bagdia@arm.com */ 7910396Sakash.bagdia@arm.com void uncondBr(void * &bp_history); 8010396Sakash.bagdia@arm.com 8110396Sakash.bagdia@arm.com /** 8210396Sakash.bagdia@arm.com * Updates the branch predictor with the actual result of a branch. 8310396Sakash.bagdia@arm.com * @param branch_addr The address of the branch to update. 8410396Sakash.bagdia@arm.com * @param taken Whether or not the branch was taken. 8510396Sakash.bagdia@arm.com * @param bp_history Pointer to the BPHistory object that was created 8610396Sakash.bagdia@arm.com * when the branch was predicted. 8710396Sakash.bagdia@arm.com */ 8810396Sakash.bagdia@arm.com void update(Addr &branch_addr, bool taken, void *bp_history); 8910396Sakash.bagdia@arm.com 9010396Sakash.bagdia@arm.com /** 9110396Sakash.bagdia@arm.com * Restores the global branch history on a squash. 9210396Sakash.bagdia@arm.com * @param bp_history Pointer to the BPHistory object that has the 9310396Sakash.bagdia@arm.com * previous global branch history in it. 9410396Sakash.bagdia@arm.com */ 9510396Sakash.bagdia@arm.com void squash(void *bp_history); 9610396Sakash.bagdia@arm.com 9710396Sakash.bagdia@arm.com /** Returns the global history. */ 9810396Sakash.bagdia@arm.com inline unsigned readGlobalHist() { return globalHistory; } 9910396Sakash.bagdia@arm.com 10010396Sakash.bagdia@arm.com private: 10110396Sakash.bagdia@arm.com /** 10210396Sakash.bagdia@arm.com * Returns if the branch should be taken or not, given a counter 10310396Sakash.bagdia@arm.com * value. 10410396Sakash.bagdia@arm.com * @param count The counter value. 10510396Sakash.bagdia@arm.com */ 10610396Sakash.bagdia@arm.com inline bool getPrediction(uint8_t &count); 10710396Sakash.bagdia@arm.com 10810396Sakash.bagdia@arm.com /** 10910396Sakash.bagdia@arm.com * Returns the local history index, given a branch address. 11010396Sakash.bagdia@arm.com * @param branch_addr The branch's PC address. 11110396Sakash.bagdia@arm.com */ 11210396Sakash.bagdia@arm.com inline unsigned calcLocHistIdx(Addr &branch_addr); 11310396Sakash.bagdia@arm.com 11410396Sakash.bagdia@arm.com /** Updates global history as taken. */ 11510396Sakash.bagdia@arm.com inline void updateGlobalHistTaken(); 11610396Sakash.bagdia@arm.com 11710396Sakash.bagdia@arm.com /** Updates global history as not taken. */ 11810396Sakash.bagdia@arm.com inline void updateGlobalHistNotTaken(); 11910396Sakash.bagdia@arm.com 12010396Sakash.bagdia@arm.com /** 12110396Sakash.bagdia@arm.com * Updates local histories as taken. 12210396Sakash.bagdia@arm.com * @param local_history_idx The local history table entry that 12310396Sakash.bagdia@arm.com * will be updated. 12410396Sakash.bagdia@arm.com */ 12510396Sakash.bagdia@arm.com inline void updateLocalHistTaken(unsigned local_history_idx); 12610396Sakash.bagdia@arm.com 12711174Sandreas.hansson@arm.com /** 12810396Sakash.bagdia@arm.com * Updates local histories as not taken. 12910396Sakash.bagdia@arm.com * @param local_history_idx The local history table entry that 13010396Sakash.bagdia@arm.com * will be updated. 13110396Sakash.bagdia@arm.com */ 13210396Sakash.bagdia@arm.com inline void updateLocalHistNotTaken(unsigned local_history_idx); 13311174Sandreas.hansson@arm.com 13410396Sakash.bagdia@arm.com /** 13511168Sandreas.hansson@arm.com * The branch history information that is created upon predicting 13611168Sandreas.hansson@arm.com * a branch. It will be passed back upon updating and squashing, 13710396Sakash.bagdia@arm.com * when the BP can use this information to update/restore its 13811174Sandreas.hansson@arm.com * state properly. 13911174Sandreas.hansson@arm.com */ 14010396Sakash.bagdia@arm.com struct BPHistory { 14110396Sakash.bagdia@arm.com#ifdef DEBUG 14210396Sakash.bagdia@arm.com BPHistory() 14310396Sakash.bagdia@arm.com { newCount++; } 14410396Sakash.bagdia@arm.com ~BPHistory() 14510396Sakash.bagdia@arm.com { newCount--; } 14610396Sakash.bagdia@arm.com 14710396Sakash.bagdia@arm.com static int newCount; 14810396Sakash.bagdia@arm.com#endif 14910396Sakash.bagdia@arm.com unsigned globalHistory; 15010396Sakash.bagdia@arm.com bool localPredTaken; 15110396Sakash.bagdia@arm.com bool globalPredTaken; 15210396Sakash.bagdia@arm.com bool globalUsed; 15310396Sakash.bagdia@arm.com }; 15410396Sakash.bagdia@arm.com 15510396Sakash.bagdia@arm.com /** Local counters. */ 15610396Sakash.bagdia@arm.com std::vector<SatCounter> localCtrs; 15710396Sakash.bagdia@arm.com 15810396Sakash.bagdia@arm.com /** Size of the local predictor. */ 15910396Sakash.bagdia@arm.com unsigned localPredictorSize; 16010396Sakash.bagdia@arm.com 16110396Sakash.bagdia@arm.com /** Mask to get the proper index bits into the predictor. */ 16210396Sakash.bagdia@arm.com unsigned localPredictorMask; 16310396Sakash.bagdia@arm.com 16410396Sakash.bagdia@arm.com /** Number of bits of the local predictor's counters. */ 16510396Sakash.bagdia@arm.com unsigned localCtrBits; 16610396Sakash.bagdia@arm.com 16710396Sakash.bagdia@arm.com /** Array of local history table entries. */ 16810396Sakash.bagdia@arm.com std::vector<unsigned> localHistoryTable; 16910396Sakash.bagdia@arm.com 17010396Sakash.bagdia@arm.com /** Size of the local history table. */ 17110396Sakash.bagdia@arm.com unsigned localHistoryTableSize; 17210396Sakash.bagdia@arm.com 17310396Sakash.bagdia@arm.com /** Number of bits for each entry of the local history table. 17410396Sakash.bagdia@arm.com * @todo Doesn't this come from the size of the local predictor? 17510396Sakash.bagdia@arm.com */ 17610396Sakash.bagdia@arm.com unsigned localHistoryBits; 17710396Sakash.bagdia@arm.com 17810396Sakash.bagdia@arm.com /** Mask to get the proper local history. */ 17910396Sakash.bagdia@arm.com unsigned localHistoryMask; 18010396Sakash.bagdia@arm.com 18110396Sakash.bagdia@arm.com /** Array of counters that make up the global predictor. */ 18210396Sakash.bagdia@arm.com std::vector<SatCounter> globalCtrs; 18310396Sakash.bagdia@arm.com 18410396Sakash.bagdia@arm.com /** Size of the global predictor. */ 18510396Sakash.bagdia@arm.com unsigned globalPredictorSize; 18610396Sakash.bagdia@arm.com 18710396Sakash.bagdia@arm.com /** Number of bits of the global predictor's counters. */ 188 unsigned globalCtrBits; 189 190 /** Global history register. */ 191 unsigned globalHistory; 192 193 /** Number of bits for the global history. */ 194 unsigned globalHistoryBits; 195 196 /** Mask to get the proper global history. */ 197 unsigned globalHistoryMask; 198 199 /** Array of counters that make up the choice predictor. */ 200 std::vector<SatCounter> choiceCtrs; 201 202 /** Size of the choice predictor (identical to the global predictor). */ 203 unsigned choicePredictorSize; 204 205 /** Number of bits of the choice predictor's counters. */ 206 unsigned choiceCtrBits; 207 208 /** Number of bits to shift the instruction over to get rid of the word 209 * offset. 210 */ 211 unsigned instShiftAmt; 212 213 /** Threshold for the counter value; above the threshold is taken, 214 * equal to or below the threshold is not taken. 215 */ 216 unsigned threshold; 217}; 218 219#endif // __CPU_O3_TOURNAMENT_PRED_HH__ 220