bpred_unit.cc revision 13626:d6a6358aa6db
1/* 2 * Copyright (c) 2011-2012, 2014 ARM Limited 3 * Copyright (c) 2010 The University of Edinburgh 4 * Copyright (c) 2012 Mark D. Hill and David A. Wood 5 * All rights reserved 6 * 7 * The license below extends only to copyright in the software and shall 8 * not be construed as granting a license to any other intellectual 9 * property including but not limited to intellectual property relating 10 * to a hardware implementation of the functionality of the software 11 * licensed hereunder. You may use the software subject to the license 12 * terms below provided that you ensure that this notice is replicated 13 * unmodified and in its entirety in all distributions of the software, 14 * modified or unmodified, in source code or in binary form. 15 * 16 * Copyright (c) 2004-2005 The Regents of The University of Michigan 17 * All rights reserved. 18 * 19 * Redistribution and use in source and binary forms, with or without 20 * modification, are permitted provided that the following conditions are 21 * met: redistributions of source code must retain the above copyright 22 * notice, this list of conditions and the following disclaimer; 23 * redistributions in binary form must reproduce the above copyright 24 * notice, this list of conditions and the following disclaimer in the 25 * documentation and/or other materials provided with the distribution; 26 * neither the name of the copyright holders nor the names of its 27 * contributors may be used to endorse or promote products derived from 28 * this software without specific prior written permission. 29 * 30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 31 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 32 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 33 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 34 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 36 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 37 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 38 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 39 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 40 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 41 * 42 * Authors: Kevin Lim 43 */ 44 45#include "cpu/pred/bpred_unit.hh" 46 47#include <algorithm> 48 49#include "arch/isa_traits.hh" 50#include "arch/types.hh" 51#include "arch/utility.hh" 52#include "base/trace.hh" 53#include "config/the_isa.hh" 54#include "debug/Branch.hh" 55 56BPredUnit::BPredUnit(const Params *params) 57 : SimObject(params), 58 numThreads(params->numThreads), 59 predHist(numThreads), 60 BTB(params->BTBEntries, 61 params->BTBTagSize, 62 params->instShiftAmt, 63 params->numThreads), 64 RAS(numThreads), 65 useIndirect(params->useIndirect), 66 iPred(params->indirectHashGHR, 67 params->indirectHashTargets, 68 params->indirectSets, 69 params->indirectWays, 70 params->indirectTagSize, 71 params->indirectPathLength, 72 params->instShiftAmt, 73 params->numThreads), 74 instShiftAmt(params->instShiftAmt) 75{ 76 for (auto& r : RAS) 77 r.init(params->RASSize); 78} 79 80void 81BPredUnit::regStats() 82{ 83 SimObject::regStats(); 84 85 lookups 86 .name(name() + ".lookups") 87 .desc("Number of BP lookups") 88 ; 89 90 condPredicted 91 .name(name() + ".condPredicted") 92 .desc("Number of conditional branches predicted") 93 ; 94 95 condIncorrect 96 .name(name() + ".condIncorrect") 97 .desc("Number of conditional branches incorrect") 98 ; 99 100 BTBLookups 101 .name(name() + ".BTBLookups") 102 .desc("Number of BTB lookups") 103 ; 104 105 BTBHits 106 .name(name() + ".BTBHits") 107 .desc("Number of BTB hits") 108 ; 109 110 BTBCorrect 111 .name(name() + ".BTBCorrect") 112 .desc("Number of correct BTB predictions (this stat may not " 113 "work properly.") 114 ; 115 116 BTBHitPct 117 .name(name() + ".BTBHitPct") 118 .desc("BTB Hit Percentage") 119 .precision(6); 120 BTBHitPct = (BTBHits / BTBLookups) * 100; 121 122 usedRAS 123 .name(name() + ".usedRAS") 124 .desc("Number of times the RAS was used to get a target.") 125 ; 126 127 RASIncorrect 128 .name(name() + ".RASInCorrect") 129 .desc("Number of incorrect RAS predictions.") 130 ; 131 132 indirectLookups 133 .name(name() + ".indirectLookups") 134 .desc("Number of indirect predictor lookups.") 135 ; 136 137 indirectHits 138 .name(name() + ".indirectHits") 139 .desc("Number of indirect target hits.") 140 ; 141 142 indirectMisses 143 .name(name() + ".indirectMisses") 144 .desc("Number of indirect misses.") 145 ; 146 147 indirectMispredicted 148 .name(name() + "indirectMispredicted") 149 .desc("Number of mispredicted indirect branches.") 150 ; 151 152} 153 154ProbePoints::PMUUPtr 155BPredUnit::pmuProbePoint(const char *name) 156{ 157 ProbePoints::PMUUPtr ptr; 158 ptr.reset(new ProbePoints::PMU(getProbeManager(), name)); 159 160 return ptr; 161} 162 163void 164BPredUnit::regProbePoints() 165{ 166 ppBranches = pmuProbePoint("Branches"); 167 ppMisses = pmuProbePoint("Misses"); 168} 169 170void 171BPredUnit::drainSanityCheck() const 172{ 173 // We shouldn't have any outstanding requests when we resume from 174 // a drained system. 175 for (const auto& ph M5_VAR_USED : predHist) 176 assert(ph.empty()); 177} 178 179bool 180BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, 181 TheISA::PCState &pc, ThreadID tid) 182{ 183 // See if branch predictor predicts taken. 184 // If so, get its target addr either from the BTB or the RAS. 185 // Save off record of branch stuff so the RAS can be fixed 186 // up once it's done. 187 188 bool pred_taken = false; 189 TheISA::PCState target = pc; 190 191 ++lookups; 192 ppBranches->notify(1); 193 194 void *bp_history = NULL; 195 196 if (inst->isUncondCtrl()) { 197 DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid); 198 pred_taken = true; 199 // Tell the BP there was an unconditional branch. 200 uncondBranch(tid, pc.instAddr(), bp_history); 201 } else { 202 ++condPredicted; 203 pred_taken = lookup(tid, pc.instAddr(), bp_history); 204 205 DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor" 206 " predicted %i for PC %s\n", tid, seqNum, pred_taken, pc); 207 } 208 209 DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history " 210 "for PC %s\n", tid, seqNum, pc); 211 212 PredictorHistory predict_record(seqNum, pc.instAddr(), 213 pred_taken, bp_history, tid, inst); 214 215 // Now lookup in the BTB or RAS. 216 if (pred_taken) { 217 if (inst->isReturn()) { 218 ++usedRAS; 219 predict_record.wasReturn = true; 220 // If it's a function return call, then look up the address 221 // in the RAS. 222 TheISA::PCState rasTop = RAS[tid].top(); 223 target = TheISA::buildRetPC(pc, rasTop); 224 225 // Record the top entry of the RAS, and its index. 226 predict_record.usedRAS = true; 227 predict_record.RASIndex = RAS[tid].topIdx(); 228 predict_record.RASTarget = rasTop; 229 230 RAS[tid].pop(); 231 232 DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, " 233 "RAS predicted target: %s, RAS index: %i.\n", 234 tid, pc, target, predict_record.RASIndex); 235 } else { 236 ++BTBLookups; 237 238 if (inst->isCall()) { 239 RAS[tid].push(pc); 240 predict_record.pushedRAS = true; 241 242 // Record that it was a call so that the top RAS entry can 243 // be popped off if the speculation is incorrect. 244 predict_record.wasCall = true; 245 246 DPRINTF(Branch, "[tid:%i]: Instruction %s was a " 247 "call, adding %s to the RAS index: %i.\n", 248 tid, pc, pc, RAS[tid].topIdx()); 249 } 250 251 if (inst->isDirectCtrl() || !useIndirect) { 252 // Check BTB on direct branches 253 if (BTB.valid(pc.instAddr(), tid)) { 254 ++BTBHits; 255 256 // If it's not a return, use the BTB to get target addr. 257 target = BTB.lookup(pc.instAddr(), tid); 258 259 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted" 260 " target is %s.\n", tid, pc, target); 261 262 } else { 263 DPRINTF(Branch, "[tid:%i]: BTB doesn't have a " 264 "valid entry.\n",tid); 265 pred_taken = false; 266 // The Direction of the branch predictor is altered 267 // because the BTB did not have an entry 268 // The predictor needs to be updated accordingly 269 if (!inst->isCall() && !inst->isReturn()) { 270 btbUpdate(tid, pc.instAddr(), bp_history); 271 DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate" 272 " called for %s\n", tid, seqNum, pc); 273 } else if (inst->isCall() && !inst->isUncondCtrl()) { 274 RAS[tid].pop(); 275 predict_record.pushedRAS = false; 276 } 277 TheISA::advancePC(target, inst); 278 } 279 } else { 280 predict_record.wasIndirect = true; 281 ++indirectLookups; 282 //Consult indirect predictor on indirect control 283 if (iPred.lookup(pc.instAddr(), getGHR(tid, bp_history), 284 target, tid)) { 285 // Indirect predictor hit 286 ++indirectHits; 287 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted " 288 "indirect target is %s.\n", tid, pc, target); 289 } else { 290 ++indirectMisses; 291 pred_taken = false; 292 DPRINTF(Branch, "[tid:%i]: Instruction %s no indirect " 293 "target.\n", tid, pc); 294 if (!inst->isCall() && !inst->isReturn()) { 295 296 } else if (inst->isCall() && !inst->isUncondCtrl()) { 297 RAS[tid].pop(); 298 predict_record.pushedRAS = false; 299 } 300 TheISA::advancePC(target, inst); 301 } 302 iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum, 303 tid); 304 } 305 } 306 } else { 307 if (inst->isReturn()) { 308 predict_record.wasReturn = true; 309 } 310 TheISA::advancePC(target, inst); 311 } 312 predict_record.target = target.instAddr(); 313 314 pc = target; 315 316 predHist[tid].push_front(predict_record); 317 318 DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added." 319 "predHist.size(): %i\n", tid, seqNum, predHist[tid].size()); 320 321 return pred_taken; 322} 323 324void 325BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid) 326{ 327 DPRINTF(Branch, "[tid:%i]: Committing branches until " 328 "[sn:%lli].\n", tid, done_sn); 329 330 iPred.commit(done_sn, tid); 331 while (!predHist[tid].empty() && 332 predHist[tid].back().seqNum <= done_sn) { 333 // Update the branch predictor with the correct results. 334 update(tid, predHist[tid].back().pc, 335 predHist[tid].back().predTaken, 336 predHist[tid].back().bpHistory, false, 337 predHist[tid].back().inst, 338 predHist[tid].back().target); 339 340 predHist[tid].pop_back(); 341 } 342} 343 344void 345BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) 346{ 347 History &pred_hist = predHist[tid]; 348 349 iPred.squash(squashed_sn, tid); 350 while (!pred_hist.empty() && 351 pred_hist.front().seqNum > squashed_sn) { 352 if (pred_hist.front().usedRAS) { 353 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i," 354 " target: %s.\n", tid, 355 pred_hist.front().RASIndex, pred_hist.front().RASTarget); 356 357 RAS[tid].restore(pred_hist.front().RASIndex, 358 pred_hist.front().RASTarget); 359 } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) { 360 // Was a call but predicated false. Pop RAS here 361 DPRINTF(Branch, "[tid: %i] Squashing" 362 " Call [sn:%i] PC: %s Popping RAS\n", tid, 363 pred_hist.front().seqNum, pred_hist.front().pc); 364 RAS[tid].pop(); 365 } 366 367 // This call should delete the bpHistory. 368 squash(tid, pred_hist.front().bpHistory); 369 370 DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] " 371 "PC %s.\n", tid, pred_hist.front().seqNum, 372 pred_hist.front().pc); 373 374 pred_hist.pop_front(); 375 376 DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n", 377 tid, predHist[tid].size()); 378 } 379} 380 381void 382BPredUnit::squash(const InstSeqNum &squashed_sn, 383 const TheISA::PCState &corrTarget, 384 bool actually_taken, ThreadID tid) 385{ 386 // Now that we know that a branch was mispredicted, we need to undo 387 // all the branches that have been seen up until this branch and 388 // fix up everything. 389 // NOTE: This should be call conceivably in 2 scenarios: 390 // (1) After an branch is executed, it updates its status in the ROB 391 // The commit stage then checks the ROB update and sends a signal to 392 // the fetch stage to squash history after the mispredict 393 // (2) In the decode stage, you can find out early if a unconditional 394 // PC-relative, branch was predicted incorrectly. If so, a signal 395 // to the fetch stage is sent to squash history after the mispredict 396 397 History &pred_hist = predHist[tid]; 398 399 ++condIncorrect; 400 ppMisses->notify(1); 401 402 DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, " 403 "setting target to %s.\n", tid, squashed_sn, corrTarget); 404 405 // Squash All Branches AFTER this mispredicted branch 406 squash(squashed_sn, tid); 407 408 // If there's a squash due to a syscall, there may not be an entry 409 // corresponding to the squash. In that case, don't bother trying to 410 // fix up the entry. 411 if (!pred_hist.empty()) { 412 413 auto hist_it = pred_hist.begin(); 414 //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(), 415 // squashed_sn); 416 417 //assert(hist_it != pred_hist.end()); 418 if (pred_hist.front().seqNum != squashed_sn) { 419 DPRINTF(Branch, "Front sn %i != Squash sn %i\n", 420 pred_hist.front().seqNum, squashed_sn); 421 422 assert(pred_hist.front().seqNum == squashed_sn); 423 } 424 425 426 if ((*hist_it).usedRAS) { 427 ++RASIncorrect; 428 DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n", 429 tid, hist_it->seqNum); 430 } 431 432 // Get the underlying Global History Register 433 unsigned ghr = getGHR(tid, hist_it->bpHistory); 434 435 // There are separate functions for in-order and out-of-order 436 // branch prediction, but not for update. Therefore, this 437 // call should take into account that the mispredicted branch may 438 // be on the wrong path (i.e., OoO execution), and that the counter 439 // counter table(s) should not be updated. Thus, this call should 440 // restore the state of the underlying predictor, for instance the 441 // local/global histories. The counter tables will be updated when 442 // the branch actually commits. 443 444 // Remember the correct direction for the update at commit. 445 pred_hist.front().predTaken = actually_taken; 446 pred_hist.front().target = corrTarget.instAddr(); 447 448 update(tid, (*hist_it).pc, actually_taken, 449 pred_hist.front().bpHistory, true, pred_hist.front().inst, 450 corrTarget.instAddr()); 451 452 if (actually_taken) { 453 if (hist_it->wasReturn && !hist_it->usedRAS) { 454 DPRINTF(Branch, "[tid: %i] Incorrectly predicted" 455 " return [sn:%i] PC: %s\n", tid, hist_it->seqNum, 456 hist_it->pc); 457 RAS[tid].pop(); 458 hist_it->usedRAS = true; 459 } 460 if (hist_it->wasIndirect) { 461 ++indirectMispredicted; 462 iPred.recordTarget(hist_it->seqNum, ghr, corrTarget, tid); 463 } else { 464 DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]" 465 " PC: %s\n", tid,hist_it->seqNum, hist_it->pc); 466 467 BTB.update((*hist_it).pc, corrTarget, tid); 468 } 469 } else { 470 //Actually not Taken 471 if (hist_it->usedRAS) { 472 DPRINTF(Branch,"[tid: %i] Incorrectly predicted" 473 " return [sn:%i] PC: %s Restoring RAS\n", tid, 474 hist_it->seqNum, hist_it->pc); 475 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS" 476 " to: %i, target: %s.\n", tid, 477 hist_it->RASIndex, hist_it->RASTarget); 478 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget); 479 hist_it->usedRAS = false; 480 } else if (hist_it->wasCall && hist_it->pushedRAS) { 481 //Was a Call but predicated false. Pop RAS here 482 DPRINTF(Branch, "[tid: %i] Incorrectly predicted" 483 " Call [sn:%i] PC: %s Popping RAS\n", tid, 484 hist_it->seqNum, hist_it->pc); 485 RAS[tid].pop(); 486 hist_it->pushedRAS = false; 487 } 488 } 489 } else { 490 DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't " 491 "update.\n", tid, squashed_sn); 492 } 493} 494 495void 496BPredUnit::dump() 497{ 498 int i = 0; 499 for (const auto& ph : predHist) { 500 if (!ph.empty()) { 501 auto pred_hist_it = ph.begin(); 502 503 cprintf("predHist[%i].size(): %i\n", i++, ph.size()); 504 505 while (pred_hist_it != ph.end()) { 506 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, " 507 "bpHistory:%#x\n", 508 pred_hist_it->seqNum, pred_hist_it->pc, 509 pred_hist_it->tid, pred_hist_it->predTaken, 510 pred_hist_it->bpHistory); 511 pred_hist_it++; 512 } 513 514 cprintf("\n"); 515 } 516 } 517} 518 519