1/* 2 * Copyright (c) 2011, 2014 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Copyright (c) 2004-2006 The Regents of The University of Michigan 15 * All rights reserved. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions are 19 * met: redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer; 21 * redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution; 24 * neither the name of the copyright holders nor the names of its 25 * contributors may be used to endorse or promote products derived from 26 * this software without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 39 * 40 * Authors: Kevin Lim 41 * Timothy M. Jones 42 * Nilay Vaish 43 */ 44 45#ifndef __CPU_PRED_TOURNAMENT_PRED_HH__ 46#define __CPU_PRED_TOURNAMENT_PRED_HH__ 47 48#include <vector> 49 50#include "base/types.hh" 51#include "cpu/pred/bpred_unit.hh" 52#include "cpu/pred/sat_counter.hh" 53#include "params/TournamentBP.hh" 54 55/** 56 * Implements a tournament branch predictor, hopefully identical to the one 57 * used in the 21264. It has a local predictor, which uses a local history 58 * table to index into a table of counters, and a global predictor, which 59 * uses a global history to index into a table of counters. A choice 60 * predictor chooses between the two. Only the global history register 61 * is speculatively updated, the rest are updated upon branches committing 62 * or misspeculating. 63 */ 64class TournamentBP : public BPredUnit 65{ 66 public: 67 /** 68 * Default branch predictor constructor. 69 */ 70 TournamentBP(const TournamentBPParams *params); 71 72 /** 73 * Looks up the given address in the branch predictor and returns 74 * a true/false value as to whether it is taken. Also creates a 75 * BPHistory object to store any state it will need on squash/update. 76 * @param branch_addr The address of the branch to look up. 77 * @param bp_history Pointer that will be set to the BPHistory object. 78 * @return Whether or not the branch is taken. 79 */
| 1/* 2 * Copyright (c) 2011, 2014 ARM Limited 3 * All rights reserved 4 * 5 * The license below extends only to copyright in the software and shall 6 * not be construed as granting a license to any other intellectual 7 * property including but not limited to intellectual property relating 8 * to a hardware implementation of the functionality of the software 9 * licensed hereunder. You may use the software subject to the license 10 * terms below provided that you ensure that this notice is replicated 11 * unmodified and in its entirety in all distributions of the software, 12 * modified or unmodified, in source code or in binary form. 13 * 14 * Copyright (c) 2004-2006 The Regents of The University of Michigan 15 * All rights reserved. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions are 19 * met: redistributions of source code must retain the above copyright 20 * notice, this list of conditions and the following disclaimer; 21 * redistributions in binary form must reproduce the above copyright 22 * notice, this list of conditions and the following disclaimer in the 23 * documentation and/or other materials provided with the distribution; 24 * neither the name of the copyright holders nor the names of its 25 * contributors may be used to endorse or promote products derived from 26 * this software without specific prior written permission. 27 * 28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 39 * 40 * Authors: Kevin Lim 41 * Timothy M. Jones 42 * Nilay Vaish 43 */ 44 45#ifndef __CPU_PRED_TOURNAMENT_PRED_HH__ 46#define __CPU_PRED_TOURNAMENT_PRED_HH__ 47 48#include <vector> 49 50#include "base/types.hh" 51#include "cpu/pred/bpred_unit.hh" 52#include "cpu/pred/sat_counter.hh" 53#include "params/TournamentBP.hh" 54 55/** 56 * Implements a tournament branch predictor, hopefully identical to the one 57 * used in the 21264. It has a local predictor, which uses a local history 58 * table to index into a table of counters, and a global predictor, which 59 * uses a global history to index into a table of counters. A choice 60 * predictor chooses between the two. Only the global history register 61 * is speculatively updated, the rest are updated upon branches committing 62 * or misspeculating. 63 */ 64class TournamentBP : public BPredUnit 65{ 66 public: 67 /** 68 * Default branch predictor constructor. 69 */ 70 TournamentBP(const TournamentBPParams *params); 71 72 /** 73 * Looks up the given address in the branch predictor and returns 74 * a true/false value as to whether it is taken. Also creates a 75 * BPHistory object to store any state it will need on squash/update. 76 * @param branch_addr The address of the branch to look up. 77 * @param bp_history Pointer that will be set to the BPHistory object. 78 * @return Whether or not the branch is taken. 79 */
|
80 bool lookup(Addr branch_addr, void * &bp_history);
| 80 bool lookup(ThreadID tid, Addr branch_addr, void * &bp_history);
|
81 82 /** 83 * Records that there was an unconditional branch, and modifies 84 * the bp history to point to an object that has the previous 85 * global history stored in it. 86 * @param bp_history Pointer that will be set to the BPHistory object. 87 */
| 81 82 /** 83 * Records that there was an unconditional branch, and modifies 84 * the bp history to point to an object that has the previous 85 * global history stored in it. 86 * @param bp_history Pointer that will be set to the BPHistory object. 87 */
|
88 void uncondBranch(Addr pc, void * &bp_history);
| 88 void uncondBranch(ThreadID tid, Addr pc, void * &bp_history);
|
89 /** 90 * Updates the branch predictor to Not Taken if a BTB entry is 91 * invalid or not found. 92 * @param branch_addr The address of the branch to look up. 93 * @param bp_history Pointer to any bp history state. 94 * @return Whether or not the branch is taken. 95 */
| 89 /** 90 * Updates the branch predictor to Not Taken if a BTB entry is 91 * invalid or not found. 92 * @param branch_addr The address of the branch to look up. 93 * @param bp_history Pointer to any bp history state. 94 * @return Whether or not the branch is taken. 95 */
|
96 void btbUpdate(Addr branch_addr, void * &bp_history);
| 96 void btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history);
|
97 /** 98 * Updates the branch predictor with the actual result of a branch. 99 * @param branch_addr The address of the branch to update. 100 * @param taken Whether or not the branch was taken. 101 * @param bp_history Pointer to the BPHistory object that was created 102 * when the branch was predicted. 103 * @param squashed is set when this function is called during a squash 104 * operation. 105 */
| 97 /** 98 * Updates the branch predictor with the actual result of a branch. 99 * @param branch_addr The address of the branch to update. 100 * @param taken Whether or not the branch was taken. 101 * @param bp_history Pointer to the BPHistory object that was created 102 * when the branch was predicted. 103 * @param squashed is set when this function is called during a squash 104 * operation. 105 */
|
106 void update(Addr branch_addr, bool taken, void *bp_history, bool squashed);
| 106 void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, 107 bool squashed);
|
107
| 108
|
108 void retireSquashed(void *bp_history);
| 109 void retireSquashed(ThreadID tid, void *bp_history);
|
109 110 /** 111 * Restores the global branch history on a squash. 112 * @param bp_history Pointer to the BPHistory object that has the 113 * previous global branch history in it. 114 */
| 110 111 /** 112 * Restores the global branch history on a squash. 113 * @param bp_history Pointer to the BPHistory object that has the 114 * previous global branch history in it. 115 */
|
115 void squash(void *bp_history);
| 116 void squash(ThreadID tid, void *bp_history);
|
116
| 117
|
117 unsigned getGHR(void *bp_history) const;
| 118 unsigned getGHR(ThreadID tid, void *bp_history) const;
|
118
| 119
|
119 /** Returns the global history. */ 120 inline unsigned readGlobalHist() { return globalHistory; } 121
| |
122 private: 123 /** 124 * Returns if the branch should be taken or not, given a counter 125 * value. 126 * @param count The counter value. 127 */ 128 inline bool getPrediction(uint8_t &count); 129 130 /** 131 * Returns the local history index, given a branch address. 132 * @param branch_addr The branch's PC address. 133 */ 134 inline unsigned calcLocHistIdx(Addr &branch_addr); 135 136 /** Updates global history as taken. */
| 120 private: 121 /** 122 * Returns if the branch should be taken or not, given a counter 123 * value. 124 * @param count The counter value. 125 */ 126 inline bool getPrediction(uint8_t &count); 127 128 /** 129 * Returns the local history index, given a branch address. 130 * @param branch_addr The branch's PC address. 131 */ 132 inline unsigned calcLocHistIdx(Addr &branch_addr); 133 134 /** Updates global history as taken. */
|
137 inline void updateGlobalHistTaken();
| 135 inline void updateGlobalHistTaken(ThreadID tid);
|
138 139 /** Updates global history as not taken. */
| 136 137 /** Updates global history as not taken. */
|
140 inline void updateGlobalHistNotTaken();
| 138 inline void updateGlobalHistNotTaken(ThreadID tid);
|
141 142 /** 143 * Updates local histories as taken. 144 * @param local_history_idx The local history table entry that 145 * will be updated. 146 */ 147 inline void updateLocalHistTaken(unsigned local_history_idx); 148 149 /** 150 * Updates local histories as not taken. 151 * @param local_history_idx The local history table entry that 152 * will be updated. 153 */ 154 inline void updateLocalHistNotTaken(unsigned local_history_idx); 155 156 /** 157 * The branch history information that is created upon predicting 158 * a branch. It will be passed back upon updating and squashing, 159 * when the BP can use this information to update/restore its 160 * state properly. 161 */ 162 struct BPHistory { 163#ifdef DEBUG 164 BPHistory() 165 { newCount++; } 166 ~BPHistory() 167 { newCount--; } 168 169 static int newCount; 170#endif 171 unsigned globalHistory; 172 unsigned localHistoryIdx; 173 unsigned localHistory; 174 bool localPredTaken; 175 bool globalPredTaken; 176 bool globalUsed; 177 }; 178 179 /** Flag for invalid predictor index */ 180 static const int invalidPredictorIndex = -1; 181 /** Local counters. */ 182 std::vector<SatCounter> localCtrs; 183 184 /** Number of counters in the local predictor. */ 185 unsigned localPredictorSize; 186 187 /** Mask to truncate values stored in the local history table. */ 188 unsigned localPredictorMask; 189 190 /** Number of bits of the local predictor's counters. */ 191 unsigned localCtrBits; 192 193 /** Array of local history table entries. */ 194 std::vector<unsigned> localHistoryTable; 195 196 /** Number of entries in the local history table. */ 197 unsigned localHistoryTableSize; 198 199 /** Number of bits for each entry of the local history table. */ 200 unsigned localHistoryBits; 201 202 /** Array of counters that make up the global predictor. */ 203 std::vector<SatCounter> globalCtrs; 204 205 /** Number of entries in the global predictor. */ 206 unsigned globalPredictorSize; 207 208 /** Number of bits of the global predictor's counters. */ 209 unsigned globalCtrBits; 210 211 /** Global history register. Contains as much history as specified by 212 * globalHistoryBits. Actual number of bits used is determined by 213 * globalHistoryMask and choiceHistoryMask. */
| 139 140 /** 141 * Updates local histories as taken. 142 * @param local_history_idx The local history table entry that 143 * will be updated. 144 */ 145 inline void updateLocalHistTaken(unsigned local_history_idx); 146 147 /** 148 * Updates local histories as not taken. 149 * @param local_history_idx The local history table entry that 150 * will be updated. 151 */ 152 inline void updateLocalHistNotTaken(unsigned local_history_idx); 153 154 /** 155 * The branch history information that is created upon predicting 156 * a branch. It will be passed back upon updating and squashing, 157 * when the BP can use this information to update/restore its 158 * state properly. 159 */ 160 struct BPHistory { 161#ifdef DEBUG 162 BPHistory() 163 { newCount++; } 164 ~BPHistory() 165 { newCount--; } 166 167 static int newCount; 168#endif 169 unsigned globalHistory; 170 unsigned localHistoryIdx; 171 unsigned localHistory; 172 bool localPredTaken; 173 bool globalPredTaken; 174 bool globalUsed; 175 }; 176 177 /** Flag for invalid predictor index */ 178 static const int invalidPredictorIndex = -1; 179 /** Local counters. */ 180 std::vector<SatCounter> localCtrs; 181 182 /** Number of counters in the local predictor. */ 183 unsigned localPredictorSize; 184 185 /** Mask to truncate values stored in the local history table. */ 186 unsigned localPredictorMask; 187 188 /** Number of bits of the local predictor's counters. */ 189 unsigned localCtrBits; 190 191 /** Array of local history table entries. */ 192 std::vector<unsigned> localHistoryTable; 193 194 /** Number of entries in the local history table. */ 195 unsigned localHistoryTableSize; 196 197 /** Number of bits for each entry of the local history table. */ 198 unsigned localHistoryBits; 199 200 /** Array of counters that make up the global predictor. */ 201 std::vector<SatCounter> globalCtrs; 202 203 /** Number of entries in the global predictor. */ 204 unsigned globalPredictorSize; 205 206 /** Number of bits of the global predictor's counters. */ 207 unsigned globalCtrBits; 208 209 /** Global history register. Contains as much history as specified by 210 * globalHistoryBits. Actual number of bits used is determined by 211 * globalHistoryMask and choiceHistoryMask. */
|
214 unsigned globalHistory;
| 212 std::vector<unsigned> globalHistory;
|
215 216 /** Number of bits for the global history. Determines maximum number of 217 entries in global and choice predictor tables. */ 218 unsigned globalHistoryBits; 219 220 /** Mask to apply to globalHistory to access global history table. 221 * Based on globalPredictorSize.*/ 222 unsigned globalHistoryMask; 223 224 /** Mask to apply to globalHistory to access choice history table. 225 * Based on choicePredictorSize.*/ 226 unsigned choiceHistoryMask; 227 228 /** Mask to control how much history is stored. All of it might not be 229 * used. */ 230 unsigned historyRegisterMask; 231 232 /** Array of counters that make up the choice predictor. */ 233 std::vector<SatCounter> choiceCtrs; 234 235 /** Number of entries in the choice predictor. */ 236 unsigned choicePredictorSize; 237 238 /** Number of bits in the choice predictor's counters. */ 239 unsigned choiceCtrBits; 240 241 /** Thresholds for the counter value; above the threshold is taken, 242 * equal to or below the threshold is not taken. 243 */ 244 unsigned localThreshold; 245 unsigned globalThreshold; 246 unsigned choiceThreshold; 247}; 248 249#endif // __CPU_PRED_TOURNAMENT_PRED_HH__
| 213 214 /** Number of bits for the global history. Determines maximum number of 215 entries in global and choice predictor tables. */ 216 unsigned globalHistoryBits; 217 218 /** Mask to apply to globalHistory to access global history table. 219 * Based on globalPredictorSize.*/ 220 unsigned globalHistoryMask; 221 222 /** Mask to apply to globalHistory to access choice history table. 223 * Based on choicePredictorSize.*/ 224 unsigned choiceHistoryMask; 225 226 /** Mask to control how much history is stored. All of it might not be 227 * used. */ 228 unsigned historyRegisterMask; 229 230 /** Array of counters that make up the choice predictor. */ 231 std::vector<SatCounter> choiceCtrs; 232 233 /** Number of entries in the choice predictor. */ 234 unsigned choicePredictorSize; 235 236 /** Number of bits in the choice predictor's counters. */ 237 unsigned choiceCtrBits; 238 239 /** Thresholds for the counter value; above the threshold is taken, 240 * equal to or below the threshold is not taken. 241 */ 242 unsigned localThreshold; 243 unsigned globalThreshold; 244 unsigned choiceThreshold; 245}; 246 247#endif // __CPU_PRED_TOURNAMENT_PRED_HH__
|