tournament.hh revision 11434:b5aed9d2d54e
111185Serfan.azarkhish@unibo.it/* 211185Serfan.azarkhish@unibo.it * Copyright (c) 2011, 2014 ARM Limited 311185Serfan.azarkhish@unibo.it * All rights reserved 411185Serfan.azarkhish@unibo.it * 511185Serfan.azarkhish@unibo.it * The license below extends only to copyright in the software and shall 611185Serfan.azarkhish@unibo.it * not be construed as granting a license to any other intellectual 711185Serfan.azarkhish@unibo.it * property including but not limited to intellectual property relating 811185Serfan.azarkhish@unibo.it * to a hardware implementation of the functionality of the software 911185Serfan.azarkhish@unibo.it * licensed hereunder. You may use the software subject to the license 1011185Serfan.azarkhish@unibo.it * terms below provided that you ensure that this notice is replicated 1111185Serfan.azarkhish@unibo.it * unmodified and in its entirety in all distributions of the software, 1211185Serfan.azarkhish@unibo.it * modified or unmodified, in source code or in binary form. 1311185Serfan.azarkhish@unibo.it * 1411185Serfan.azarkhish@unibo.it * Copyright (c) 2004-2006 The Regents of The University of Michigan 1511185Serfan.azarkhish@unibo.it * All rights reserved. 1611185Serfan.azarkhish@unibo.it * 1711185Serfan.azarkhish@unibo.it * Redistribution and use in source and binary forms, with or without 1811185Serfan.azarkhish@unibo.it * modification, are permitted provided that the following conditions are 1911185Serfan.azarkhish@unibo.it * met: redistributions of source code must retain the above copyright 2011185Serfan.azarkhish@unibo.it * notice, this list of conditions and the following disclaimer; 2111185Serfan.azarkhish@unibo.it * redistributions in binary form must reproduce the above copyright 2211185Serfan.azarkhish@unibo.it * notice, this list of conditions and the following disclaimer in the 2311185Serfan.azarkhish@unibo.it * documentation and/or other materials provided with the distribution; 2411185Serfan.azarkhish@unibo.it * neither the name of the copyright holders nor the names of its 2511185Serfan.azarkhish@unibo.it * contributors may be used to endorse or promote products derived from 2611185Serfan.azarkhish@unibo.it * this software without specific prior written permission. 2711185Serfan.azarkhish@unibo.it * 2811185Serfan.azarkhish@unibo.it * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2911185Serfan.azarkhish@unibo.it * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 3011185Serfan.azarkhish@unibo.it * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 3111185Serfan.azarkhish@unibo.it * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 3211185Serfan.azarkhish@unibo.it * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 3311185Serfan.azarkhish@unibo.it * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 3411185Serfan.azarkhish@unibo.it * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 3511185Serfan.azarkhish@unibo.it * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3611185Serfan.azarkhish@unibo.it * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3711185Serfan.azarkhish@unibo.it * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3811185Serfan.azarkhish@unibo.it * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3911185Serfan.azarkhish@unibo.it * 4011185Serfan.azarkhish@unibo.it * Authors: Kevin Lim 4111185Serfan.azarkhish@unibo.it * Timothy M. Jones 4211185Serfan.azarkhish@unibo.it * Nilay Vaish 4311185Serfan.azarkhish@unibo.it */ 4411185Serfan.azarkhish@unibo.it 4511185Serfan.azarkhish@unibo.it#ifndef __CPU_PRED_TOURNAMENT_PRED_HH__ 4611185Serfan.azarkhish@unibo.it#define __CPU_PRED_TOURNAMENT_PRED_HH__ 4711185Serfan.azarkhish@unibo.it 4811185Serfan.azarkhish@unibo.it#include <vector> 4911185Serfan.azarkhish@unibo.it 5011185Serfan.azarkhish@unibo.it#include "base/types.hh" 5111185Serfan.azarkhish@unibo.it#include "cpu/pred/bpred_unit.hh" 5211185Serfan.azarkhish@unibo.it#include "cpu/pred/sat_counter.hh" 5311185Serfan.azarkhish@unibo.it#include "params/TournamentBP.hh" 5411185Serfan.azarkhish@unibo.it 5511185Serfan.azarkhish@unibo.it/** 5611185Serfan.azarkhish@unibo.it * Implements a tournament branch predictor, hopefully identical to the one 5711185Serfan.azarkhish@unibo.it * used in the 21264. It has a local predictor, which uses a local history 5811185Serfan.azarkhish@unibo.it * table to index into a table of counters, and a global predictor, which 5911185Serfan.azarkhish@unibo.it * uses a global history to index into a table of counters. A choice 6011185Serfan.azarkhish@unibo.it * predictor chooses between the two. Only the global history register 6111185Serfan.azarkhish@unibo.it * is speculatively updated, the rest are updated upon branches committing 6211185Serfan.azarkhish@unibo.it * or misspeculating. 6311185Serfan.azarkhish@unibo.it */ 6411185Serfan.azarkhish@unibo.itclass TournamentBP : public BPredUnit 6511185Serfan.azarkhish@unibo.it{ 6611185Serfan.azarkhish@unibo.it public: 6711185Serfan.azarkhish@unibo.it /** 6811185Serfan.azarkhish@unibo.it * Default branch predictor constructor. 6912084Sspwilson2@wisc.edu */ 7012084Sspwilson2@wisc.edu TournamentBP(const TournamentBPParams *params); 7111185Serfan.azarkhish@unibo.it 7211185Serfan.azarkhish@unibo.it /** 7311185Serfan.azarkhish@unibo.it * Looks up the given address in the branch predictor and returns 7411185Serfan.azarkhish@unibo.it * a true/false value as to whether it is taken. Also creates a 7511185Serfan.azarkhish@unibo.it * BPHistory object to store any state it will need on squash/update. 7611185Serfan.azarkhish@unibo.it * @param branch_addr The address of the branch to look up. 7711185Serfan.azarkhish@unibo.it * @param bp_history Pointer that will be set to the BPHistory object. 7811185Serfan.azarkhish@unibo.it * @return Whether or not the branch is taken. 7911185Serfan.azarkhish@unibo.it */ 8012084Sspwilson2@wisc.edu bool lookup(ThreadID tid, Addr branch_addr, void * &bp_history); 8111185Serfan.azarkhish@unibo.it 8211185Serfan.azarkhish@unibo.it /** 8311185Serfan.azarkhish@unibo.it * Records that there was an unconditional branch, and modifies 8411185Serfan.azarkhish@unibo.it * the bp history to point to an object that has the previous 8511185Serfan.azarkhish@unibo.it * global history stored in it. 8611185Serfan.azarkhish@unibo.it * @param bp_history Pointer that will be set to the BPHistory object. 8711185Serfan.azarkhish@unibo.it */ 8811185Serfan.azarkhish@unibo.it void uncondBranch(ThreadID tid, Addr pc, void * &bp_history); 8911185Serfan.azarkhish@unibo.it /** 9011551Sabdul.mutaal@gmail.com * Updates the branch predictor to Not Taken if a BTB entry is 9111551Sabdul.mutaal@gmail.com * invalid or not found. 9211551Sabdul.mutaal@gmail.com * @param branch_addr The address of the branch to look up. 9311185Serfan.azarkhish@unibo.it * @param bp_history Pointer to any bp history state. 9411185Serfan.azarkhish@unibo.it * @return Whether or not the branch is taken. 9511185Serfan.azarkhish@unibo.it */ 9611185Serfan.azarkhish@unibo.it void btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history); 9711185Serfan.azarkhish@unibo.it /** 9811185Serfan.azarkhish@unibo.it * Updates the branch predictor with the actual result of a branch. 9911185Serfan.azarkhish@unibo.it * @param branch_addr The address of the branch to update. 10011185Serfan.azarkhish@unibo.it * @param taken Whether or not the branch was taken. 10111185Serfan.azarkhish@unibo.it * @param bp_history Pointer to the BPHistory object that was created 10211185Serfan.azarkhish@unibo.it * when the branch was predicted. 10311185Serfan.azarkhish@unibo.it * @param squashed is set when this function is called during a squash 10411185Serfan.azarkhish@unibo.it * operation. 10511185Serfan.azarkhish@unibo.it */ 10611185Serfan.azarkhish@unibo.it void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, 10711185Serfan.azarkhish@unibo.it bool squashed); 10811185Serfan.azarkhish@unibo.it 10911185Serfan.azarkhish@unibo.it void retireSquashed(ThreadID tid, void *bp_history); 11011185Serfan.azarkhish@unibo.it 11111185Serfan.azarkhish@unibo.it /** 11211185Serfan.azarkhish@unibo.it * Restores the global branch history on a squash. 11311185Serfan.azarkhish@unibo.it * @param bp_history Pointer to the BPHistory object that has the 11411185Serfan.azarkhish@unibo.it * previous global branch history in it. 11511185Serfan.azarkhish@unibo.it */ 11611185Serfan.azarkhish@unibo.it void squash(ThreadID tid, void *bp_history); 11711185Serfan.azarkhish@unibo.it 11811185Serfan.azarkhish@unibo.it unsigned getGHR(ThreadID tid, void *bp_history) const; 11911185Serfan.azarkhish@unibo.it 12011185Serfan.azarkhish@unibo.it private: 12111185Serfan.azarkhish@unibo.it /** 12211185Serfan.azarkhish@unibo.it * Returns if the branch should be taken or not, given a counter 12311185Serfan.azarkhish@unibo.it * value. 12411185Serfan.azarkhish@unibo.it * @param count The counter value. 12511185Serfan.azarkhish@unibo.it */ 12611185Serfan.azarkhish@unibo.it inline bool getPrediction(uint8_t &count); 12711185Serfan.azarkhish@unibo.it 12811185Serfan.azarkhish@unibo.it /** 12911185Serfan.azarkhish@unibo.it * Returns the local history index, given a branch address. 13011185Serfan.azarkhish@unibo.it * @param branch_addr The branch's PC address. 13111185Serfan.azarkhish@unibo.it */ 13211185Serfan.azarkhish@unibo.it inline unsigned calcLocHistIdx(Addr &branch_addr); 13311185Serfan.azarkhish@unibo.it 13411185Serfan.azarkhish@unibo.it /** Updates global history as taken. */ 13511185Serfan.azarkhish@unibo.it inline void updateGlobalHistTaken(ThreadID tid); 13611185Serfan.azarkhish@unibo.it 13711185Serfan.azarkhish@unibo.it /** Updates global history as not taken. */ 13811185Serfan.azarkhish@unibo.it inline void updateGlobalHistNotTaken(ThreadID tid); 13911185Serfan.azarkhish@unibo.it 14011185Serfan.azarkhish@unibo.it /** 14111185Serfan.azarkhish@unibo.it * Updates local histories as taken. 14211185Serfan.azarkhish@unibo.it * @param local_history_idx The local history table entry that 14311185Serfan.azarkhish@unibo.it * will be updated. 14411185Serfan.azarkhish@unibo.it */ 14511185Serfan.azarkhish@unibo.it inline void updateLocalHistTaken(unsigned local_history_idx); 14611185Serfan.azarkhish@unibo.it 14711185Serfan.azarkhish@unibo.it /** 14811185Serfan.azarkhish@unibo.it * Updates local histories as not taken. 14911185Serfan.azarkhish@unibo.it * @param local_history_idx The local history table entry that 15011185Serfan.azarkhish@unibo.it * will be updated. 15111185Serfan.azarkhish@unibo.it */ 15211185Serfan.azarkhish@unibo.it inline void updateLocalHistNotTaken(unsigned local_history_idx); 15311185Serfan.azarkhish@unibo.it 15411185Serfan.azarkhish@unibo.it /** 15511185Serfan.azarkhish@unibo.it * The branch history information that is created upon predicting 15611185Serfan.azarkhish@unibo.it * a branch. It will be passed back upon updating and squashing, 15711185Serfan.azarkhish@unibo.it * when the BP can use this information to update/restore its 15811551Sabdul.mutaal@gmail.com * state properly. 15911551Sabdul.mutaal@gmail.com */ 16011551Sabdul.mutaal@gmail.com struct BPHistory { 16111185Serfan.azarkhish@unibo.it#ifdef DEBUG 16211185Serfan.azarkhish@unibo.it BPHistory() 16311185Serfan.azarkhish@unibo.it { newCount++; } 16411185Serfan.azarkhish@unibo.it ~BPHistory() 16511185Serfan.azarkhish@unibo.it { newCount--; } 16611185Serfan.azarkhish@unibo.it 16711185Serfan.azarkhish@unibo.it static int newCount; 16811185Serfan.azarkhish@unibo.it#endif 16911185Serfan.azarkhish@unibo.it unsigned globalHistory; 17011185Serfan.azarkhish@unibo.it unsigned localHistoryIdx; 17111185Serfan.azarkhish@unibo.it unsigned localHistory; 17211185Serfan.azarkhish@unibo.it bool localPredTaken; 17311185Serfan.azarkhish@unibo.it bool globalPredTaken; 17411185Serfan.azarkhish@unibo.it bool globalUsed; 17511185Serfan.azarkhish@unibo.it }; 17611185Serfan.azarkhish@unibo.it 17711185Serfan.azarkhish@unibo.it /** Flag for invalid predictor index */ 17811185Serfan.azarkhish@unibo.it static const int invalidPredictorIndex = -1; 17911185Serfan.azarkhish@unibo.it /** Local counters. */ 18011185Serfan.azarkhish@unibo.it std::vector<SatCounter> localCtrs; 18111185Serfan.azarkhish@unibo.it 18211185Serfan.azarkhish@unibo.it /** Number of counters in the local predictor. */ 18311185Serfan.azarkhish@unibo.it unsigned localPredictorSize; 18411185Serfan.azarkhish@unibo.it 18511185Serfan.azarkhish@unibo.it /** Mask to truncate values stored in the local history table. */ 18611185Serfan.azarkhish@unibo.it unsigned localPredictorMask; 18711185Serfan.azarkhish@unibo.it 18811185Serfan.azarkhish@unibo.it /** Number of bits of the local predictor's counters. */ 18911185Serfan.azarkhish@unibo.it unsigned localCtrBits; 19011185Serfan.azarkhish@unibo.it 19111284Sandreas.hansson@arm.com /** Array of local history table entries. */ 19211185Serfan.azarkhish@unibo.it std::vector<unsigned> localHistoryTable; 19311185Serfan.azarkhish@unibo.it 19411185Serfan.azarkhish@unibo.it /** Number of entries in the local history table. */ 19511185Serfan.azarkhish@unibo.it unsigned localHistoryTableSize; 19611185Serfan.azarkhish@unibo.it 19711185Serfan.azarkhish@unibo.it /** Number of bits for each entry of the local history table. */ 19811185Serfan.azarkhish@unibo.it unsigned localHistoryBits; 19911185Serfan.azarkhish@unibo.it 20011185Serfan.azarkhish@unibo.it /** Array of counters that make up the global predictor. */ 20111185Serfan.azarkhish@unibo.it std::vector<SatCounter> globalCtrs; 20211185Serfan.azarkhish@unibo.it 20311185Serfan.azarkhish@unibo.it /** Number of entries in the global predictor. */ 20411185Serfan.azarkhish@unibo.it unsigned globalPredictorSize; 20511185Serfan.azarkhish@unibo.it 20611185Serfan.azarkhish@unibo.it /** Number of bits of the global predictor's counters. */ 20711185Serfan.azarkhish@unibo.it unsigned globalCtrBits; 20811185Serfan.azarkhish@unibo.it 20911185Serfan.azarkhish@unibo.it /** Global history register. Contains as much history as specified by 21011185Serfan.azarkhish@unibo.it * globalHistoryBits. Actual number of bits used is determined by 21111185Serfan.azarkhish@unibo.it * globalHistoryMask and choiceHistoryMask. */ 21211185Serfan.azarkhish@unibo.it std::vector<unsigned> globalHistory; 21311185Serfan.azarkhish@unibo.it 21411185Serfan.azarkhish@unibo.it /** Number of bits for the global history. Determines maximum number of 21511185Serfan.azarkhish@unibo.it entries in global and choice predictor tables. */ 21611185Serfan.azarkhish@unibo.it unsigned globalHistoryBits; 21711185Serfan.azarkhish@unibo.it 21811185Serfan.azarkhish@unibo.it /** Mask to apply to globalHistory to access global history table. 21911185Serfan.azarkhish@unibo.it * Based on globalPredictorSize.*/ 22011551Sabdul.mutaal@gmail.com unsigned globalHistoryMask; 22111185Serfan.azarkhish@unibo.it 22211185Serfan.azarkhish@unibo.it /** Mask to apply to globalHistory to access choice history table. 22311185Serfan.azarkhish@unibo.it * Based on choicePredictorSize.*/ 22411185Serfan.azarkhish@unibo.it unsigned choiceHistoryMask; 22511185Serfan.azarkhish@unibo.it 22611185Serfan.azarkhish@unibo.it /** Mask to control how much history is stored. All of it might not be 22711185Serfan.azarkhish@unibo.it * used. */ 22811185Serfan.azarkhish@unibo.it unsigned historyRegisterMask; 22911185Serfan.azarkhish@unibo.it 23011185Serfan.azarkhish@unibo.it /** Array of counters that make up the choice predictor. */ 23111185Serfan.azarkhish@unibo.it std::vector<SatCounter> choiceCtrs; 23211185Serfan.azarkhish@unibo.it 23311185Serfan.azarkhish@unibo.it /** Number of entries in the choice predictor. */ 23411185Serfan.azarkhish@unibo.it unsigned choicePredictorSize; 23511185Serfan.azarkhish@unibo.it 23611185Serfan.azarkhish@unibo.it /** Number of bits in the choice predictor's counters. */ 23711185Serfan.azarkhish@unibo.it unsigned choiceCtrBits; 23811185Serfan.azarkhish@unibo.it 23911185Serfan.azarkhish@unibo.it /** Thresholds for the counter value; above the threshold is taken, 24011185Serfan.azarkhish@unibo.it * equal to or below the threshold is not taken. 24111185Serfan.azarkhish@unibo.it */ 24211185Serfan.azarkhish@unibo.it unsigned localThreshold; 24311185Serfan.azarkhish@unibo.it unsigned globalThreshold; 24411185Serfan.azarkhish@unibo.it unsigned choiceThreshold; 24511185Serfan.azarkhish@unibo.it}; 24611185Serfan.azarkhish@unibo.it 24711185Serfan.azarkhish@unibo.it#endif // __CPU_PRED_TOURNAMENT_PRED_HH__ 24811185Serfan.azarkhish@unibo.it