tournament.hh revision 2345
110915Sandreas.sandberg@arm.com/* 210915Sandreas.sandberg@arm.com * Copyright (c) 2004-2006 The Regents of The University of Michigan 310915Sandreas.sandberg@arm.com * All rights reserved. 410915Sandreas.sandberg@arm.com * 510915Sandreas.sandberg@arm.com * Redistribution and use in source and binary forms, with or without 610915Sandreas.sandberg@arm.com * modification, are permitted provided that the following conditions are 710915Sandreas.sandberg@arm.com * met: redistributions of source code must retain the above copyright 810915Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer; 910915Sandreas.sandberg@arm.com * redistributions in binary form must reproduce the above copyright 1010915Sandreas.sandberg@arm.com * notice, this list of conditions and the following disclaimer in the 1110915Sandreas.sandberg@arm.com * documentation and/or other materials provided with the distribution; 1210915Sandreas.sandberg@arm.com * neither the name of the copyright holders nor the names of its 1310915Sandreas.sandberg@arm.com * contributors may be used to endorse or promote products derived from 1410915Sandreas.sandberg@arm.com * this software without specific prior written permission. 1510915Sandreas.sandberg@arm.com * 1610915Sandreas.sandberg@arm.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1710915Sandreas.sandberg@arm.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1810915Sandreas.sandberg@arm.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1910915Sandreas.sandberg@arm.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2010915Sandreas.sandberg@arm.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2110915Sandreas.sandberg@arm.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2210915Sandreas.sandberg@arm.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2310915Sandreas.sandberg@arm.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2410915Sandreas.sandberg@arm.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2510915Sandreas.sandberg@arm.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2610915Sandreas.sandberg@arm.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2710915Sandreas.sandberg@arm.com */ 2810915Sandreas.sandberg@arm.com 2910915Sandreas.sandberg@arm.com#ifndef __CPU_O3_TOURNAMENT_PRED_HH__ 3010915Sandreas.sandberg@arm.com#define __CPU_O3_TOURNAMENT_PRED_HH__ 3110915Sandreas.sandberg@arm.com 3210915Sandreas.sandberg@arm.com// For Addr type. 3310915Sandreas.sandberg@arm.com#include "arch/isa_traits.hh" 3410915Sandreas.sandberg@arm.com#include "cpu/o3/sat_counter.hh" 3510915Sandreas.sandberg@arm.com#include <vector> 3610915Sandreas.sandberg@arm.com 3710915Sandreas.sandberg@arm.com/** 3810915Sandreas.sandberg@arm.com * Implements a tournament branch predictor, hopefully identical to the one 3910915Sandreas.sandberg@arm.com * used in the 21264. It has a local predictor, which uses a local history 4010915Sandreas.sandberg@arm.com * table to index into a table of counters, and a global predictor, which 4110915Sandreas.sandberg@arm.com * uses a global history to index into a table of counters. A choice 4210915Sandreas.sandberg@arm.com * predictor chooses between the two. Only the global history register 4310915Sandreas.sandberg@arm.com * is speculatively updated, the rest are updated upon branches committing 4410915Sandreas.sandberg@arm.com * or misspeculating. 4510915Sandreas.sandberg@arm.com */ 4610915Sandreas.sandberg@arm.comclass TournamentBP 4710915Sandreas.sandberg@arm.com{ 4810915Sandreas.sandberg@arm.com public: 4910915Sandreas.sandberg@arm.com /** 5010915Sandreas.sandberg@arm.com * Default branch predictor constructor. 5110915Sandreas.sandberg@arm.com */ 5210915Sandreas.sandberg@arm.com TournamentBP(unsigned localPredictorSize, 5310915Sandreas.sandberg@arm.com unsigned localCtrBits, 5410915Sandreas.sandberg@arm.com unsigned localHistoryTableSize, 5510915Sandreas.sandberg@arm.com unsigned localHistoryBits, 5610915Sandreas.sandberg@arm.com unsigned globalPredictorSize, 5710915Sandreas.sandberg@arm.com unsigned globalHistoryBits, 5810915Sandreas.sandberg@arm.com unsigned globalCtrBits, 5910915Sandreas.sandberg@arm.com unsigned choicePredictorSize, 6010915Sandreas.sandberg@arm.com unsigned choiceCtrBits, 6110915Sandreas.sandberg@arm.com unsigned instShiftAmt); 6210915Sandreas.sandberg@arm.com 6310915Sandreas.sandberg@arm.com /** 6410915Sandreas.sandberg@arm.com * Looks up the given address in the branch predictor and returns 6510915Sandreas.sandberg@arm.com * a true/false value as to whether it is taken. Also creates a 6610915Sandreas.sandberg@arm.com * BPHistory object to store any state it will need on squash/update. 6710915Sandreas.sandberg@arm.com * @param branch_addr The address of the branch to look up. 6810915Sandreas.sandberg@arm.com * @param bp_history Pointer that will be set to the BPHistory object. 6910915Sandreas.sandberg@arm.com * @return Whether or not the branch is taken. 7010915Sandreas.sandberg@arm.com */ 7110915Sandreas.sandberg@arm.com bool lookup(Addr &branch_addr, void * &bp_history); 7210915Sandreas.sandberg@arm.com 7310915Sandreas.sandberg@arm.com /** 7410915Sandreas.sandberg@arm.com * Records that there was an unconditional branch, and modifies 7510915Sandreas.sandberg@arm.com * the bp history to point to an object that has the previous 7610915Sandreas.sandberg@arm.com * global history stored in it. 7710915Sandreas.sandberg@arm.com * @param bp_history Pointer that will be set to the BPHistory object. 7810915Sandreas.sandberg@arm.com */ 7910915Sandreas.sandberg@arm.com void uncondBr(void * &bp_history); 8010915Sandreas.sandberg@arm.com 8110915Sandreas.sandberg@arm.com /** 8210915Sandreas.sandberg@arm.com * Updates the branch predictor with the actual result of a branch. 8310915Sandreas.sandberg@arm.com * @param branch_addr The address of the branch to update. 8410915Sandreas.sandberg@arm.com * @param taken Whether or not the branch was taken. 8510915Sandreas.sandberg@arm.com * @param bp_history Pointer to the BPHistory object that was created 8610915Sandreas.sandberg@arm.com * when the branch was predicted. 8710915Sandreas.sandberg@arm.com */ 8810915Sandreas.sandberg@arm.com void update(Addr &branch_addr, bool taken, void *bp_history); 8910915Sandreas.sandberg@arm.com 9010915Sandreas.sandberg@arm.com /** 9110915Sandreas.sandberg@arm.com * Restores the global branch history on a squash. 9210915Sandreas.sandberg@arm.com * @param bp_history Pointer to the BPHistory object that has the 9310915Sandreas.sandberg@arm.com * previous global branch history in it. 9410915Sandreas.sandberg@arm.com */ 9510915Sandreas.sandberg@arm.com void squash(void *bp_history); 9610915Sandreas.sandberg@arm.com 9710915Sandreas.sandberg@arm.com /** Returns the global history. */ 9810915Sandreas.sandberg@arm.com inline unsigned readGlobalHist() { return globalHistory; } 9910915Sandreas.sandberg@arm.com 10010915Sandreas.sandberg@arm.com private: 10110915Sandreas.sandberg@arm.com /** 10210915Sandreas.sandberg@arm.com * Returns if the branch should be taken or not, given a counter 10310915Sandreas.sandberg@arm.com * value. 10410915Sandreas.sandberg@arm.com * @param count The counter value. 10510915Sandreas.sandberg@arm.com */ 10610915Sandreas.sandberg@arm.com inline bool getPrediction(uint8_t &count); 10710915Sandreas.sandberg@arm.com 10810915Sandreas.sandberg@arm.com /** 10910915Sandreas.sandberg@arm.com * Returns the local history index, given a branch address. 11010915Sandreas.sandberg@arm.com * @param branch_addr The branch's PC address. 11110915Sandreas.sandberg@arm.com */ 11210915Sandreas.sandberg@arm.com inline unsigned calcLocHistIdx(Addr &branch_addr); 11310915Sandreas.sandberg@arm.com 11410915Sandreas.sandberg@arm.com /** Updates global history as taken. */ 11510915Sandreas.sandberg@arm.com inline void updateGlobalHistTaken(); 11610915Sandreas.sandberg@arm.com 11710915Sandreas.sandberg@arm.com /** Updates global history as not taken. */ 11810915Sandreas.sandberg@arm.com inline void updateGlobalHistNotTaken(); 11910915Sandreas.sandberg@arm.com 12010915Sandreas.sandberg@arm.com /** 12110915Sandreas.sandberg@arm.com * Updates local histories as taken. 12210915Sandreas.sandberg@arm.com * @param local_history_idx The local history table entry that 12310915Sandreas.sandberg@arm.com * will be updated. 12410915Sandreas.sandberg@arm.com */ 12510915Sandreas.sandberg@arm.com inline void updateLocalHistTaken(unsigned local_history_idx); 12610915Sandreas.sandberg@arm.com 12710915Sandreas.sandberg@arm.com /** 12810915Sandreas.sandberg@arm.com * Updates local histories as not taken. 12910915Sandreas.sandberg@arm.com * @param local_history_idx The local history table entry that 13010915Sandreas.sandberg@arm.com * will be updated. 13110915Sandreas.sandberg@arm.com */ 13210915Sandreas.sandberg@arm.com inline void updateLocalHistNotTaken(unsigned local_history_idx); 13310915Sandreas.sandberg@arm.com 13410915Sandreas.sandberg@arm.com /** 13510915Sandreas.sandberg@arm.com * The branch history information that is created upon predicting 13610915Sandreas.sandberg@arm.com * a branch. It will be passed back upon updating and squashing, 13710915Sandreas.sandberg@arm.com * when the BP can use this information to update/restore its 13810915Sandreas.sandberg@arm.com * state properly. 13910915Sandreas.sandberg@arm.com */ 14010915Sandreas.sandberg@arm.com struct BPHistory { 14110915Sandreas.sandberg@arm.com#ifdef DEBUG 14210915Sandreas.sandberg@arm.com BPHistory() 14310915Sandreas.sandberg@arm.com { newCount++; } 14410915Sandreas.sandberg@arm.com ~BPHistory() 14510915Sandreas.sandberg@arm.com { newCount--; } 14610915Sandreas.sandberg@arm.com 14710915Sandreas.sandberg@arm.com static int newCount; 14810915Sandreas.sandberg@arm.com#endif 14910915Sandreas.sandberg@arm.com unsigned globalHistory; 15010915Sandreas.sandberg@arm.com bool localPredTaken; 15110915Sandreas.sandberg@arm.com bool globalPredTaken; 15210915Sandreas.sandberg@arm.com bool globalUsed; 15310915Sandreas.sandberg@arm.com }; 15410915Sandreas.sandberg@arm.com 15510915Sandreas.sandberg@arm.com /** Local counters. */ 15610915Sandreas.sandberg@arm.com std::vector<SatCounter> localCtrs; 15710915Sandreas.sandberg@arm.com 15810915Sandreas.sandberg@arm.com /** Size of the local predictor. */ 15910915Sandreas.sandberg@arm.com unsigned localPredictorSize; 16010915Sandreas.sandberg@arm.com 16110915Sandreas.sandberg@arm.com /** Number of bits of the local predictor's counters. */ 16210915Sandreas.sandberg@arm.com unsigned localCtrBits; 16310915Sandreas.sandberg@arm.com 16410915Sandreas.sandberg@arm.com /** Array of local history table entries. */ 16510915Sandreas.sandberg@arm.com std::vector<unsigned> localHistoryTable; 16610915Sandreas.sandberg@arm.com 16710915Sandreas.sandberg@arm.com /** Size of the local history table. */ 16810915Sandreas.sandberg@arm.com unsigned localHistoryTableSize; 16910915Sandreas.sandberg@arm.com 17010915Sandreas.sandberg@arm.com /** Number of bits for each entry of the local history table. 17110915Sandreas.sandberg@arm.com * @todo Doesn't this come from the size of the local predictor? 17210915Sandreas.sandberg@arm.com */ 17310915Sandreas.sandberg@arm.com unsigned localHistoryBits; 17410915Sandreas.sandberg@arm.com 17510915Sandreas.sandberg@arm.com /** Mask to get the proper local history. */ 17610915Sandreas.sandberg@arm.com unsigned localHistoryMask; 17710915Sandreas.sandberg@arm.com 17810915Sandreas.sandberg@arm.com /** Array of counters that make up the global predictor. */ 17910915Sandreas.sandberg@arm.com std::vector<SatCounter> globalCtrs; 18010915Sandreas.sandberg@arm.com 18110915Sandreas.sandberg@arm.com /** Size of the global predictor. */ 18210915Sandreas.sandberg@arm.com unsigned globalPredictorSize; 18310915Sandreas.sandberg@arm.com 18410915Sandreas.sandberg@arm.com /** Number of bits of the global predictor's counters. */ 18510915Sandreas.sandberg@arm.com unsigned globalCtrBits; 18610915Sandreas.sandberg@arm.com 18710915Sandreas.sandberg@arm.com /** Global history register. */ 18810915Sandreas.sandberg@arm.com unsigned globalHistory; 18910915Sandreas.sandberg@arm.com 19010915Sandreas.sandberg@arm.com /** Number of bits for the global history. */ 19110915Sandreas.sandberg@arm.com unsigned globalHistoryBits; 19210915Sandreas.sandberg@arm.com 19310915Sandreas.sandberg@arm.com /** Mask to get the proper global history. */ 19410915Sandreas.sandberg@arm.com unsigned globalHistoryMask; 19510915Sandreas.sandberg@arm.com 19610915Sandreas.sandberg@arm.com /** Array of counters that make up the choice predictor. */ 19710915Sandreas.sandberg@arm.com std::vector<SatCounter> choiceCtrs; 19810915Sandreas.sandberg@arm.com 19910915Sandreas.sandberg@arm.com /** Size of the choice predictor (identical to the global predictor). */ 20010915Sandreas.sandberg@arm.com unsigned choicePredictorSize; 20110915Sandreas.sandberg@arm.com 20210915Sandreas.sandberg@arm.com /** Number of bits of the choice predictor's counters. */ 203 unsigned choiceCtrBits; 204 205 /** Number of bits to shift the instruction over to get rid of the word 206 * offset. 207 */ 208 unsigned instShiftAmt; 209 210 /** Threshold for the counter value; above the threshold is taken, 211 * equal to or below the threshold is not taken. 212 */ 213 unsigned threshold; 214}; 215 216#endif // __CPU_O3_TOURNAMENT_PRED_HH__ 217