tournament.cc revision 13626
12810SN/A/* 22810SN/A * Copyright (c) 2011, 2014 ARM Limited 32810SN/A * All rights reserved 42810SN/A * 52810SN/A * The license below extends only to copyright in the software and shall 62810SN/A * not be construed as granting a license to any other intellectual 72810SN/A * property including but not limited to intellectual property relating 82810SN/A * to a hardware implementation of the functionality of the software 92810SN/A * licensed hereunder. You may use the software subject to the license 102810SN/A * terms below provided that you ensure that this notice is replicated 112810SN/A * unmodified and in its entirety in all distributions of the software, 122810SN/A * modified or unmodified, in source code or in binary form. 132810SN/A * 142810SN/A * Copyright (c) 2004-2006 The Regents of The University of Michigan 152810SN/A * All rights reserved. 162810SN/A * 172810SN/A * Redistribution and use in source and binary forms, with or without 182810SN/A * modification, are permitted provided that the following conditions are 192810SN/A * met: redistributions of source code must retain the above copyright 202810SN/A * notice, this list of conditions and the following disclaimer; 212810SN/A * redistributions in binary form must reproduce the above copyright 222810SN/A * notice, this list of conditions and the following disclaimer in the 232810SN/A * documentation and/or other materials provided with the distribution; 242810SN/A * neither the name of the copyright holders nor the names of its 252810SN/A * contributors may be used to endorse or promote products derived from 262810SN/A * this software without specific prior written permission. 272810SN/A * 282810SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 292810SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 302810SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 312810SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 322810SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 332810SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 342810SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 352810SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 362810SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 372810SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 382810SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 394626SN/A * 404626SN/A * Authors: Kevin Lim 415314SN/A */ 422810SN/A 432810SN/A#include "cpu/pred/tournament.hh" 444626SN/A 454626SN/A#include "base/bitfield.hh" 462810SN/A#include "base/intmath.hh" 472810SN/A 482810SN/ATournamentBP::TournamentBP(const TournamentBPParams *params) 493374SN/A : BPredUnit(params), 502810SN/A localPredictorSize(params->localPredictorSize), 515314SN/A localCtrBits(params->localCtrBits), 524626SN/A localHistoryTableSize(params->localHistoryTableSize), 534626SN/A localHistoryBits(ceilLog2(params->localPredictorSize)), 542810SN/A globalPredictorSize(params->globalPredictorSize), 554626SN/A globalCtrBits(params->globalCtrBits), 564626SN/A globalHistory(params->numThreads, 0), 574626SN/A globalHistoryBits( 585875Ssteve.reinhardt@amd.com ceilLog2(params->globalPredictorSize) > 595875Ssteve.reinhardt@amd.com ceilLog2(params->choicePredictorSize) ? 605875Ssteve.reinhardt@amd.com ceilLog2(params->globalPredictorSize) : 615875Ssteve.reinhardt@amd.com ceilLog2(params->choicePredictorSize)), 625875Ssteve.reinhardt@amd.com choicePredictorSize(params->choicePredictorSize), 635875Ssteve.reinhardt@amd.com choiceCtrBits(params->choiceCtrBits) 645875Ssteve.reinhardt@amd.com{ 654871SN/A if (!isPowerOf2(localPredictorSize)) { 664871SN/A fatal("Invalid local predictor size!\n"); 674666SN/A } 684626SN/A 695875Ssteve.reinhardt@amd.com if (!isPowerOf2(globalPredictorSize)) { 705318SN/A fatal("Invalid global predictor size!\n"); 715318SN/A } 724626SN/A 735318SN/A //Set up the array of counters for the local predictor 745875Ssteve.reinhardt@amd.com localCtrs.resize(localPredictorSize); 754871SN/A 765875Ssteve.reinhardt@amd.com for (int i = 0; i < localPredictorSize; ++i) 774626SN/A localCtrs[i].setBits(localCtrBits); 784626SN/A 794626SN/A localPredictorMask = mask(localHistoryBits); 804903SN/A 814903SN/A if (!isPowerOf2(localHistoryTableSize)) { 824903SN/A fatal("Invalid local history table size!\n"); 835314SN/A } 844903SN/A 854903SN/A //Setup the history table for the local table 864903SN/A localHistoryTable.resize(localHistoryTableSize); 874903SN/A 884903SN/A for (int i = 0; i < localHistoryTableSize; ++i) 894903SN/A localHistoryTable[i] = 0; 904903SN/A 914903SN/A //Setup the array of counters for the global predictor 925318SN/A globalCtrs.resize(globalPredictorSize); 935875Ssteve.reinhardt@amd.com 944903SN/A for (int i = 0; i < globalPredictorSize; ++i) 954908SN/A globalCtrs[i].setBits(globalCtrBits); 964920SN/A 975314SN/A // Set up the global history mask 985314SN/A // this is equivalent to mask(log2(globalPredictorSize) 994903SN/A globalHistoryMask = globalPredictorSize - 1; 1004903SN/A 1012810SN/A if (!isPowerOf2(choicePredictorSize)) { 1022810SN/A fatal("Invalid choice predictor size!\n"); 1032810SN/A } 1042810SN/A 1052810SN/A // Set up choiceHistoryMask 1062810SN/A // this is equivalent to mask(log2(choicePredictorSize) 1072810SN/A choiceHistoryMask = choicePredictorSize - 1; 1084626SN/A 1094626SN/A //Setup the array of counters for the choice predictor 1104626SN/A choiceCtrs.resize(choicePredictorSize); 1114666SN/A 1124871SN/A for (int i = 0; i < choicePredictorSize; ++i) 1134666SN/A choiceCtrs[i].setBits(choiceCtrBits); 1144666SN/A 1154666SN/A //Set up historyRegisterMask 1164666SN/A historyRegisterMask = mask(globalHistoryBits); 1174626SN/A 1182810SN/A //Check that predictors don't use more bits than they have available 1194626SN/A if (globalHistoryMask > historyRegisterMask) { 1204626SN/A fatal("Global predictor too large for global history bits!\n"); 1214626SN/A } 1224626SN/A if (choiceHistoryMask > historyRegisterMask) { 1233374SN/A fatal("Choice predictor too large for global history bits!\n"); 1242810SN/A } 1254626SN/A 1265730SSteve.Reinhardt@amd.com if (globalHistoryMask < historyRegisterMask && 1275730SSteve.Reinhardt@amd.com choiceHistoryMask < historyRegisterMask) { 1284903SN/A inform("More global history bits than required by predictors\n"); 1294626SN/A } 1305314SN/A 1314665SN/A // Set thresholds for the three predictors' counters 1324626SN/A // This is equivalent to (2^(Ctr))/2 - 1 1334626SN/A localThreshold = (ULL(1) << (localCtrBits - 1)) - 1; 1344626SN/A globalThreshold = (ULL(1) << (globalCtrBits - 1)) - 1; 1354908SN/A choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1; 1364908SN/A} 1374665SN/A 1384670SN/Ainline 1394665SN/Aunsigned 1402810SN/ATournamentBP::calcLocHistIdx(Addr &branch_addr) 1414626SN/A{ 1422810SN/A // Get low order bits after removing instruction offset. 1432810SN/A return (branch_addr >> instShiftAmt) & (localHistoryTableSize - 1); 1442810SN/A} 1454668SN/A 1464668SN/Ainline 1474668SN/Avoid 1484668SN/ATournamentBP::updateGlobalHistTaken(ThreadID tid) 1494668SN/A{ 1502810SN/A globalHistory[tid] = (globalHistory[tid] << 1) | 1; 1512810SN/A globalHistory[tid] = globalHistory[tid] & historyRegisterMask; 1522810SN/A} 1532810SN/A 1542810SN/Ainline 1554626SN/Avoid 1562810SN/ATournamentBP::updateGlobalHistNotTaken(ThreadID tid) 1572810SN/A{ 1582810SN/A globalHistory[tid] = (globalHistory[tid] << 1); 1592810SN/A globalHistory[tid] = globalHistory[tid] & historyRegisterMask; 1602810SN/A} 1612810SN/A 1622810SN/Ainline 1633374SN/Avoid 1644903SN/ATournamentBP::updateLocalHistTaken(unsigned local_history_idx) 1652810SN/A{ 1664903SN/A localHistoryTable[local_history_idx] = 1674665SN/A (localHistoryTable[local_history_idx] << 1) | 1; 1682810SN/A} 1694626SN/A 1704626SN/Ainline 1714626SN/Avoid 1722810SN/ATournamentBP::updateLocalHistNotTaken(unsigned local_history_idx) 1732810SN/A{ 1743374SN/A localHistoryTable[local_history_idx] = 1752810SN/A (localHistoryTable[local_history_idx] << 1); 1762810SN/A} 1773374SN/A 1782982SN/A 1792810SN/Avoid 1804666SN/ATournamentBP::btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history) 1814666SN/A{ 1822810SN/A unsigned local_history_idx = calcLocHistIdx(branch_addr); 1834908SN/A //Update Global History to Not Taken (clear LSB) 1844908SN/A globalHistory[tid] &= (historyRegisterMask & ~ULL(1)); 1855318SN/A //Update Local History to Not Taken 1865318SN/A localHistoryTable[local_history_idx] = 1872810SN/A localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1)); 1882810SN/A} 1892810SN/A 1902810SN/Abool 1912810SN/ATournamentBP::lookup(ThreadID tid, Addr branch_addr, void * &bp_history) 1922810SN/A{ 1933374SN/A bool local_prediction; 1942810SN/A unsigned local_history_idx; 1952810SN/A unsigned local_predictor_idx; 1964666SN/A 1974902SN/A bool global_prediction; 1982810SN/A bool choice_prediction; 1992810SN/A 2002810SN/A //Lookup in the local predictor to get its branch prediction 2012810SN/A local_history_idx = calcLocHistIdx(branch_addr); 2022810SN/A local_predictor_idx = localHistoryTable[local_history_idx] 2032810SN/A & localPredictorMask; 2042810SN/A local_prediction = localCtrs[local_predictor_idx].read() > localThreshold; 2052810SN/A 2062810SN/A //Lookup in the global predictor to get its branch prediction 2072810SN/A global_prediction = globalThreshold < 2085730SSteve.Reinhardt@amd.com globalCtrs[globalHistory[tid] & globalHistoryMask].read(); 2092810SN/A 2102810SN/A //Lookup in the choice predictor to see which one to use 2112810SN/A choice_prediction = choiceThreshold < 2122810SN/A choiceCtrs[globalHistory[tid] & choiceHistoryMask].read(); 2132810SN/A 2144903SN/A // Create BPHistory and pass it back to be recorded. 2152810SN/A BPHistory *history = new BPHistory; 2162810SN/A history->globalHistory = globalHistory[tid]; 2174899SN/A history->localPredTaken = local_prediction; 2184899SN/A history->globalPredTaken = global_prediction; 2194899SN/A history->globalUsed = choice_prediction; 2205730SSteve.Reinhardt@amd.com history->localHistoryIdx = local_history_idx; 2214899SN/A history->localHistory = local_predictor_idx; 2224899SN/A bp_history = (void *)history; 2232810SN/A 2242810SN/A assert(local_history_idx < localHistoryTableSize); 2252810SN/A 2265730SSteve.Reinhardt@amd.com // Speculative update of the global history and the 2275730SSteve.Reinhardt@amd.com // selected local history. 2285730SSteve.Reinhardt@amd.com if (choice_prediction) { 2295730SSteve.Reinhardt@amd.com if (global_prediction) { 2305730SSteve.Reinhardt@amd.com updateGlobalHistTaken(tid); 2312810SN/A updateLocalHistTaken(local_history_idx); 2322810SN/A return true; 2332810SN/A } else { 2342810SN/A updateGlobalHistNotTaken(tid); 2352810SN/A updateLocalHistNotTaken(local_history_idx); 2362810SN/A return false; 2372810SN/A } 2384903SN/A } else { 2392810SN/A if (local_prediction) { 2402810SN/A updateGlobalHistTaken(tid); 2415730SSteve.Reinhardt@amd.com updateLocalHistTaken(local_history_idx); 2422810SN/A return true; 2434630SN/A } else { 2444630SN/A updateGlobalHistNotTaken(tid); 2454630SN/A updateLocalHistNotTaken(local_history_idx); 2465875Ssteve.reinhardt@amd.com return false; 2472810SN/A } 2482810SN/A } 2494665SN/A} 2504665SN/A 2514671SN/Avoid 2524668SN/ATournamentBP::uncondBranch(ThreadID tid, Addr pc, void * &bp_history) 2535314SN/A{ 2544920SN/A // Create BPHistory and pass it back to be recorded. 2552810SN/A BPHistory *history = new BPHistory; 2565314SN/A history->globalHistory = globalHistory[tid]; 2572810SN/A history->localPredTaken = true; 2585314SN/A history->globalPredTaken = true; 2595314SN/A history->globalUsed = true; 2605314SN/A history->localHistoryIdx = invalidPredictorIndex; 2612810SN/A history->localHistory = invalidPredictorIndex; 2622810SN/A bp_history = static_cast<void *>(history); 2632810SN/A 264 updateGlobalHistTaken(tid); 265} 266 267void 268TournamentBP::update(ThreadID tid, Addr branch_addr, bool taken, 269 void *bp_history, bool squashed, 270 const StaticInstPtr & inst, Addr corrTarget) 271{ 272 assert(bp_history); 273 274 BPHistory *history = static_cast<BPHistory *>(bp_history); 275 276 unsigned local_history_idx = calcLocHistIdx(branch_addr); 277 278 assert(local_history_idx < localHistoryTableSize); 279 280 // Unconditional branches do not use local history. 281 bool old_local_pred_valid = history->localHistory != 282 invalidPredictorIndex; 283 284 // If this is a misprediction, restore the speculatively 285 // updated state (global history register and local history) 286 // and update again. 287 if (squashed) { 288 // Global history restore and update 289 globalHistory[tid] = (history->globalHistory << 1) | taken; 290 globalHistory[tid] &= historyRegisterMask; 291 292 // Local history restore and update. 293 if (old_local_pred_valid) { 294 localHistoryTable[local_history_idx] = 295 (history->localHistory << 1) | taken; 296 } 297 298 return; 299 } 300 301 unsigned old_local_pred_index = history->localHistory & 302 localPredictorMask; 303 304 assert(old_local_pred_index < localPredictorSize); 305 306 // Update the choice predictor to tell it which one was correct if 307 // there was a prediction. 308 if (history->localPredTaken != history->globalPredTaken && 309 old_local_pred_valid) 310 { 311 // If the local prediction matches the actual outcome, 312 // decrement the counter. Otherwise increment the 313 // counter. 314 unsigned choice_predictor_idx = 315 history->globalHistory & choiceHistoryMask; 316 if (history->localPredTaken == taken) { 317 choiceCtrs[choice_predictor_idx].decrement(); 318 } else if (history->globalPredTaken == taken) { 319 choiceCtrs[choice_predictor_idx].increment(); 320 } 321 } 322 323 // Update the counters with the proper 324 // resolution of the branch. Histories are updated 325 // speculatively, restored upon squash() calls, and 326 // recomputed upon update(squash = true) calls, 327 // so they do not need to be updated. 328 unsigned global_predictor_idx = 329 history->globalHistory & globalHistoryMask; 330 if (taken) { 331 globalCtrs[global_predictor_idx].increment(); 332 if (old_local_pred_valid) { 333 localCtrs[old_local_pred_index].increment(); 334 } 335 } else { 336 globalCtrs[global_predictor_idx].decrement(); 337 if (old_local_pred_valid) { 338 localCtrs[old_local_pred_index].decrement(); 339 } 340 } 341 342 // We're done with this history, now delete it. 343 delete history; 344} 345 346void 347TournamentBP::squash(ThreadID tid, void *bp_history) 348{ 349 BPHistory *history = static_cast<BPHistory *>(bp_history); 350 351 // Restore global history to state prior to this branch. 352 globalHistory[tid] = history->globalHistory; 353 354 // Restore local history 355 if (history->localHistoryIdx != invalidPredictorIndex) { 356 localHistoryTable[history->localHistoryIdx] = history->localHistory; 357 } 358 359 // Delete this BPHistory now that we're done with it. 360 delete history; 361} 362 363TournamentBP* 364TournamentBPParams::create() 365{ 366 return new TournamentBP(this); 367} 368 369unsigned 370TournamentBP::getGHR(ThreadID tid, void *bp_history) const 371{ 372 return static_cast<BPHistory *>(bp_history)->globalHistory; 373} 374 375#ifdef DEBUG 376int 377TournamentBP::BPHistory::newCount = 0; 378#endif 379