src/cpu/pred/tournament.hh - public/gem5 - Git at Google

 /*
  * Copyright (c) 2011, 2014 ARM Limited
  * All rights reserved
  *
  * The license below extends only to copyright in the software and shall
  * not be construed as granting a license to any other intellectual
  * property including but not limited to intellectual property relating
  * to a hardware implementation of the functionality of the software
  * licensed hereunder.  You may use the software subject to the license
  * terms below provided that you ensure that this notice is replicated
  * unmodified and in its entirety in all distributions of the software,
  * modified or unmodified, in source code or in binary form.
  *
  * Copyright (c) 2004-2006 The Regents of The University of Michigan
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met: redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer;
  * redistributions in binary form must reproduce the above copyright
  * notice, this list of conditions and the following disclaimer in the
  * documentation and/or other materials provided with the distribution;
  * neither the name of the copyright holders nor the names of its
  * contributors may be used to endorse or promote products derived from
  * this software without specific prior written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  *
  * Authors: Kevin Lim
  *          Timothy M. Jones
  *          Nilay Vaish
  */

 #ifndef __CPU_PRED_TOURNAMENT_PRED_HH__
 #define __CPU_PRED_TOURNAMENT_PRED_HH__

 #include <vector>

 #include "base/sat_counter.hh"
 #include "base/types.hh"
 #include "cpu/pred/bpred_unit.hh"
 #include "params/TournamentBP.hh"

 /**
  * Implements a tournament branch predictor, hopefully identical to the one
  * used in the 21264.  It has a local predictor, which uses a local history
  * table to index into a table of counters, and a global predictor, which
  * uses a global history to index into a table of counters.  A choice
  * predictor chooses between the two.  Both the global history register
  * and the selected local history are speculatively updated.
  */
 class TournamentBP : public BPredUnit
 {
   public:
     /**
      * Default branch predictor constructor.
      */
     TournamentBP(const TournamentBPParams *params);

     /**
      * Looks up the given address in the branch predictor and returns
      * a true/false value as to whether it is taken.  Also creates a
      * BPHistory object to store any state it will need on squash/update.
      * @param branch_addr The address of the branch to look up.
      * @param bp_history Pointer that will be set to the BPHistory object.
      * @return Whether or not the branch is taken.
      */
     bool lookup(ThreadID tid, Addr branch_addr, void * &bp_history);

     /**
      * Records that there was an unconditional branch, and modifies
      * the bp history to point to an object that has the previous
      * global history stored in it.
      * @param bp_history Pointer that will be set to the BPHistory object.
      */
     void uncondBranch(ThreadID tid, Addr pc, void * &bp_history);
     /**
      * Updates the branch predictor to Not Taken if a BTB entry is
      * invalid or not found.
      * @param branch_addr The address of the branch to look up.
      * @param bp_history Pointer to any bp history state.
      * @return Whether or not the branch is taken.
      */
     void btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history);
     /**
      * Updates the branch predictor with the actual result of a branch.
      * @param branch_addr The address of the branch to update.
      * @param taken Whether or not the branch was taken.
      * @param bp_history Pointer to the BPHistory object that was created
      * when the branch was predicted.
      * @param squashed is set when this function is called during a squash
      * operation.
      * @param inst Static instruction information
      * @param corrTarget Resolved target of the branch (only needed if
      * squashed)
      */
     void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history,
                 bool squashed, const StaticInstPtr & inst, Addr corrTarget);

     /**
      * Restores the global branch history on a squash.
      * @param bp_history Pointer to the BPHistory object that has the
      * previous global branch history in it.
      */
     void squash(ThreadID tid, void *bp_history);

   private:
     /**
      * Returns if the branch should be taken or not, given a counter
      * value.
      * @param count The counter value.
      */
     inline bool getPrediction(uint8_t &count);

     /**
      * Returns the local history index, given a branch address.
      * @param branch_addr The branch's PC address.
      */
     inline unsigned calcLocHistIdx(Addr &branch_addr);

     /** Updates global history as taken. */
     inline void updateGlobalHistTaken(ThreadID tid);

     /** Updates global history as not taken. */
     inline void updateGlobalHistNotTaken(ThreadID tid);

     /**
      * Updates local histories as taken.
      * @param local_history_idx The local history table entry that
      * will be updated.
      */
     inline void updateLocalHistTaken(unsigned local_history_idx);

     /**
      * Updates local histories as not taken.
      * @param local_history_idx The local history table entry that
      * will be updated.
      */
     inline void updateLocalHistNotTaken(unsigned local_history_idx);

     /**
      * The branch history information that is created upon predicting
      * a branch.  It will be passed back upon updating and squashing,
      * when the BP can use this information to update/restore its
      * state properly.
      */
     struct BPHistory {
 #ifdef DEBUG
         BPHistory()
         { newCount++; }
         ~BPHistory()
         { newCount--; }

         static int newCount;
 #endif
         unsigned globalHistory;
         unsigned localHistoryIdx;
         unsigned localHistory;
         bool localPredTaken;
         bool globalPredTaken;
         bool globalUsed;
     };

     /** Flag for invalid predictor index */
     static const int invalidPredictorIndex = -1;
     /** Number of counters in the local predictor. */
     unsigned localPredictorSize;

     /** Mask to truncate values stored in the local history table. */
     unsigned localPredictorMask;

     /** Number of bits of the local predictor's counters. */
     unsigned localCtrBits;

     /** Local counters. */
     std::vector<SatCounter> localCtrs;

     /** Array of local history table entries. */
     std::vector<unsigned> localHistoryTable;

     /** Number of entries in the local history table. */
     unsigned localHistoryTableSize;

     /** Number of bits for each entry of the local history table. */
     unsigned localHistoryBits;

     /** Number of entries in the global predictor. */
     unsigned globalPredictorSize;

     /** Number of bits of the global predictor's counters. */
     unsigned globalCtrBits;

     /** Array of counters that make up the global predictor. */
     std::vector<SatCounter> globalCtrs;

     /** Global history register. Contains as much history as specified by
      *  globalHistoryBits. Actual number of bits used is determined by
      *  globalHistoryMask and choiceHistoryMask. */
     std::vector<unsigned> globalHistory;

     /** Number of bits for the global history. Determines maximum number of
         entries in global and choice predictor tables. */
     unsigned globalHistoryBits;

     /** Mask to apply to globalHistory to access global history table.
      *  Based on globalPredictorSize.*/
     unsigned globalHistoryMask;

     /** Mask to apply to globalHistory to access choice history table.
      *  Based on choicePredictorSize.*/
     unsigned choiceHistoryMask;

     /** Mask to control how much history is stored. All of it might not be
      *  used. */
     unsigned historyRegisterMask;

     /** Number of entries in the choice predictor. */
     unsigned choicePredictorSize;

     /** Number of bits in the choice predictor's counters. */
     unsigned choiceCtrBits;

     /** Array of counters that make up the choice predictor. */
     std::vector<SatCounter> choiceCtrs;

     /** Thresholds for the counter value; above the threshold is taken,
      *  equal to or below the threshold is not taken.
      */
     unsigned localThreshold;
     unsigned globalThreshold;
     unsigned choiceThreshold;
 };

 #endif // __CPU_PRED_TOURNAMENT_PRED_HH__
	/*
	* Copyright (c) 2011, 2014 ARM Limited
	* All rights reserved
	*
	* The license below extends only to copyright in the software and shall
	* not be construed as granting a license to any other intellectual
	* property including but not limited to intellectual property relating
	* to a hardware implementation of the functionality of the software
	* licensed hereunder. You may use the software subject to the license
	* terms below provided that you ensure that this notice is replicated
	* unmodified and in its entirety in all distributions of the software,
	* modified or unmodified, in source code or in binary form.
	*
	* Copyright (c) 2004-2006 The Regents of The University of Michigan
	* All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions are
	* met: redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer;
	* redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution;
	* neither the name of the copyright holders nor the names of its
	* contributors may be used to endorse or promote products derived from
	* this software without specific prior written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
	* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
	* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
	* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
	* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*
	* Authors: Kevin Lim
	* Timothy M. Jones
	* Nilay Vaish
	*/

	#ifndef __CPU_PRED_TOURNAMENT_PRED_HH__
	#define __CPU_PRED_TOURNAMENT_PRED_HH__

	#include <vector>

	#include "base/sat_counter.hh"
	#include "base/types.hh"
	#include "cpu/pred/bpred_unit.hh"
	#include "params/TournamentBP.hh"

	/**
	* Implements a tournament branch predictor, hopefully identical to the one
	* used in the 21264. It has a local predictor, which uses a local history
	* table to index into a table of counters, and a global predictor, which
	* uses a global history to index into a table of counters. A choice
	* predictor chooses between the two. Both the global history register
	* and the selected local history are speculatively updated.
	*/
	class TournamentBP : public BPredUnit
	{
	public:
	/**
	* Default branch predictor constructor.
	*/
	TournamentBP(const TournamentBPParams *params);

	/**
	* Looks up the given address in the branch predictor and returns
	* a true/false value as to whether it is taken. Also creates a
	* BPHistory object to store any state it will need on squash/update.
	* @param branch_addr The address of the branch to look up.
	* @param bp_history Pointer that will be set to the BPHistory object.
	* @return Whether or not the branch is taken.
	*/
	bool lookup(ThreadID tid, Addr branch_addr, void * &bp_history);

	/**
	* Records that there was an unconditional branch, and modifies
	* the bp history to point to an object that has the previous
	* global history stored in it.
	* @param bp_history Pointer that will be set to the BPHistory object.
	*/
	void uncondBranch(ThreadID tid, Addr pc, void * &bp_history);
	/**
	* Updates the branch predictor to Not Taken if a BTB entry is
	* invalid or not found.
	* @param branch_addr The address of the branch to look up.
	* @param bp_history Pointer to any bp history state.
	* @return Whether or not the branch is taken.
	*/
	void btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history);
	/**
	* Updates the branch predictor with the actual result of a branch.
	* @param branch_addr The address of the branch to update.
	* @param taken Whether or not the branch was taken.
	* @param bp_history Pointer to the BPHistory object that was created
	* when the branch was predicted.
	* @param squashed is set when this function is called during a squash
	* operation.
	* @param inst Static instruction information
	* @param corrTarget Resolved target of the branch (only needed if
	* squashed)
	*/
	void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history,
	bool squashed, const StaticInstPtr & inst, Addr corrTarget);

	/**
	* Restores the global branch history on a squash.
	* @param bp_history Pointer to the BPHistory object that has the
	* previous global branch history in it.
	*/
	void squash(ThreadID tid, void *bp_history);

	private:
	/**
	* Returns if the branch should be taken or not, given a counter
	* value.
	* @param count The counter value.
	*/
	inline bool getPrediction(uint8_t &count);

	/**
	* Returns the local history index, given a branch address.
	* @param branch_addr The branch's PC address.
	*/
	inline unsigned calcLocHistIdx(Addr &branch_addr);

	/** Updates global history as taken. */
	inline void updateGlobalHistTaken(ThreadID tid);

	/** Updates global history as not taken. */
	inline void updateGlobalHistNotTaken(ThreadID tid);

	/**
	* Updates local histories as taken.
	* @param local_history_idx The local history table entry that
	* will be updated.
	*/
	inline void updateLocalHistTaken(unsigned local_history_idx);

	/**
	* Updates local histories as not taken.
	* @param local_history_idx The local history table entry that
	* will be updated.
	*/
	inline void updateLocalHistNotTaken(unsigned local_history_idx);

	/**
	* The branch history information that is created upon predicting
	* a branch. It will be passed back upon updating and squashing,
	* when the BP can use this information to update/restore its
	* state properly.
	*/
	struct BPHistory {
	#ifdef DEBUG
	BPHistory()
	{ newCount++; }
	~BPHistory()
	{ newCount--; }

	static int newCount;
	#endif
	unsigned globalHistory;
	unsigned localHistoryIdx;
	unsigned localHistory;
	bool localPredTaken;
	bool globalPredTaken;
	bool globalUsed;
	};

	/** Flag for invalid predictor index */
	static const int invalidPredictorIndex = -1;
	/** Number of counters in the local predictor. */
	unsigned localPredictorSize;

	/** Mask to truncate values stored in the local history table. */
	unsigned localPredictorMask;

	/** Number of bits of the local predictor's counters. */
	unsigned localCtrBits;

	/** Local counters. */
	std::vector<SatCounter> localCtrs;

	/** Array of local history table entries. */
	std::vector<unsigned> localHistoryTable;

	/** Number of entries in the local history table. */
	unsigned localHistoryTableSize;

	/** Number of bits for each entry of the local history table. */
	unsigned localHistoryBits;

	/** Number of entries in the global predictor. */
	unsigned globalPredictorSize;

	/** Number of bits of the global predictor's counters. */
	unsigned globalCtrBits;

	/** Array of counters that make up the global predictor. */
	std::vector<SatCounter> globalCtrs;

	/** Global history register. Contains as much history as specified by
	* globalHistoryBits. Actual number of bits used is determined by
	* globalHistoryMask and choiceHistoryMask. */
	std::vector<unsigned> globalHistory;

	/** Number of bits for the global history. Determines maximum number of
	entries in global and choice predictor tables. */
	unsigned globalHistoryBits;

	/** Mask to apply to globalHistory to access global history table.
	* Based on globalPredictorSize.*/
	unsigned globalHistoryMask;

	/** Mask to apply to globalHistory to access choice history table.
	* Based on choicePredictorSize.*/
	unsigned choiceHistoryMask;

	/** Mask to control how much history is stored. All of it might not be
	* used. */
	unsigned historyRegisterMask;

	/** Number of entries in the choice predictor. */
	unsigned choicePredictorSize;

	/** Number of bits in the choice predictor's counters. */
	unsigned choiceCtrBits;

	/** Array of counters that make up the choice predictor. */
	std::vector<SatCounter> choiceCtrs;

	/** Thresholds for the counter value; above the threshold is taken,
	* equal to or below the threshold is not taken.
	*/
	unsigned localThreshold;
	unsigned globalThreshold;
	unsigned choiceThreshold;
	};

	#endif // __CPU_PRED_TOURNAMENT_PRED_HH__