bpred_unit.cc revision 11523
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); 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 313 pc = target; 314 315 predHist[tid].push_front(predict_record); 316 317 DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added." 318 "predHist.size(): %i\n", tid, seqNum, predHist[tid].size()); 319 320 return pred_taken; 321} 322 323bool 324BPredUnit::predictInOrder(const StaticInstPtr &inst, const InstSeqNum &seqNum, 325 int asid, TheISA::PCState &instPC, 326 TheISA::PCState &predPC, ThreadID tid) 327{ 328 // See if branch predictor predicts taken. 329 // If so, get its target addr either from the BTB or the RAS. 330 // Save off record of branch stuff so the RAS can be fixed 331 // up once it's done. 332 333 using TheISA::MachInst; 334 335 bool pred_taken = false; 336 TheISA::PCState target; 337 338 ++lookups; 339 ppBranches->notify(1); 340 341 DPRINTF(Branch, "[tid:%i] [sn:%i] %s ... PC %s doing branch " 342 "prediction\n", tid, seqNum, 343 inst->disassemble(instPC.instAddr()), instPC); 344 345 void *bp_history = NULL; 346 347 if (inst->isUncondCtrl()) { 348 DPRINTF(Branch, "[tid:%i] Unconditional control.\n", tid); 349 pred_taken = true; 350 // Tell the BP there was an unconditional branch. 351 uncondBranch(tid, instPC.instAddr(), bp_history); 352 353 if (inst->isReturn() && RAS[tid].empty()) { 354 DPRINTF(Branch, "[tid:%i] RAS is empty, predicting " 355 "false.\n", tid); 356 pred_taken = false; 357 } 358 } else { 359 ++condPredicted; 360 361 pred_taken = lookup(tid, predPC.instAddr(), bp_history); 362 } 363 364 PredictorHistory predict_record(seqNum, predPC.instAddr(), pred_taken, 365 bp_history, tid); 366 367 // Now lookup in the BTB or RAS. 368 if (pred_taken) { 369 if (inst->isReturn()) { 370 ++usedRAS; 371 372 // If it's a function return call, then look up the address 373 // in the RAS. 374 TheISA::PCState rasTop = RAS[tid].top(); 375 target = TheISA::buildRetPC(instPC, rasTop); 376 377 // Record the top entry of the RAS, and its index. 378 predict_record.usedRAS = true; 379 predict_record.RASIndex = RAS[tid].topIdx(); 380 predict_record.RASTarget = rasTop; 381 382 assert(predict_record.RASIndex < 16); 383 384 RAS[tid].pop(); 385 386 DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, " 387 "RAS predicted target: %s, RAS index: %i.\n", 388 tid, instPC, target, 389 predict_record.RASIndex); 390 } else { 391 ++BTBLookups; 392 393 if (inst->isCall()) { 394 395 RAS[tid].push(instPC); 396 predict_record.pushedRAS = true; 397 398 // Record that it was a call so that the top RAS entry can 399 // be popped off if the speculation is incorrect. 400 predict_record.wasCall = true; 401 402 DPRINTF(Branch, "[tid:%i]: Instruction %s was a call" 403 ", adding %s to the RAS index: %i.\n", 404 tid, instPC, predPC, 405 RAS[tid].topIdx()); 406 } 407 408 if (inst->isCall() && 409 inst->isUncondCtrl() && 410 inst->isDirectCtrl()) { 411 target = inst->branchTarget(instPC); 412 } else if (BTB.valid(predPC.instAddr(), asid)) { 413 ++BTBHits; 414 415 // If it's not a return, use the BTB to get the target addr. 416 target = BTB.lookup(predPC.instAddr(), asid); 417 418 DPRINTF(Branch, "[tid:%i]: [asid:%i] Instruction %s " 419 "predicted target is %s.\n", 420 tid, asid, instPC, target); 421 } else { 422 DPRINTF(Branch, "[tid:%i]: BTB doesn't have a " 423 "valid entry, predicting false.\n",tid); 424 pred_taken = false; 425 } 426 } 427 } 428 429 if (pred_taken) { 430 // Set the PC and the instruction's predicted target. 431 predPC = target; 432 } 433 DPRINTF(Branch, "[tid:%i]: [sn:%i]: Setting Predicted PC to %s.\n", 434 tid, seqNum, predPC); 435 436 predHist[tid].push_front(predict_record); 437 438 DPRINTF(Branch, "[tid:%i] [sn:%i] pushed onto front of predHist " 439 "...predHist.size(): %i\n", 440 tid, seqNum, predHist[tid].size()); 441 442 return pred_taken; 443} 444 445void 446BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid) 447{ 448 DPRINTF(Branch, "[tid:%i]: Committing branches until " 449 "[sn:%lli].\n", tid, done_sn); 450 451 iPred.commit(done_sn, tid); 452 while (!predHist[tid].empty() && 453 predHist[tid].back().seqNum <= done_sn) { 454 // Update the branch predictor with the correct results. 455 if (!predHist[tid].back().wasSquashed) { 456 update(tid, predHist[tid].back().pc, 457 predHist[tid].back().predTaken, 458 predHist[tid].back().bpHistory, false); 459 } else { 460 retireSquashed(tid, predHist[tid].back().bpHistory); 461 } 462 463 predHist[tid].pop_back(); 464 } 465} 466 467void 468BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) 469{ 470 History &pred_hist = predHist[tid]; 471 472 iPred.squash(squashed_sn, tid); 473 while (!pred_hist.empty() && 474 pred_hist.front().seqNum > squashed_sn) { 475 if (pred_hist.front().usedRAS) { 476 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i," 477 " target: %s.\n", tid, 478 pred_hist.front().RASIndex, pred_hist.front().RASTarget); 479 480 RAS[tid].restore(pred_hist.front().RASIndex, 481 pred_hist.front().RASTarget); 482 } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) { 483 // Was a call but predicated false. Pop RAS here 484 DPRINTF(Branch, "[tid: %i] Squashing" 485 " Call [sn:%i] PC: %s Popping RAS\n", tid, 486 pred_hist.front().seqNum, pred_hist.front().pc); 487 RAS[tid].pop(); 488 } 489 490 // This call should delete the bpHistory. 491 squash(tid, pred_hist.front().bpHistory); 492 493 DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] " 494 "PC %s.\n", tid, pred_hist.front().seqNum, 495 pred_hist.front().pc); 496 497 pred_hist.pop_front(); 498 499 DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n", 500 tid, predHist[tid].size()); 501 } 502} 503 504void 505BPredUnit::squash(const InstSeqNum &squashed_sn, 506 const TheISA::PCState &corrTarget, 507 bool actually_taken, ThreadID tid) 508{ 509 // Now that we know that a branch was mispredicted, we need to undo 510 // all the branches that have been seen up until this branch and 511 // fix up everything. 512 // NOTE: This should be call conceivably in 2 scenarios: 513 // (1) After an branch is executed, it updates its status in the ROB 514 // The commit stage then checks the ROB update and sends a signal to 515 // the fetch stage to squash history after the mispredict 516 // (2) In the decode stage, you can find out early if a unconditional 517 // PC-relative, branch was predicted incorrectly. If so, a signal 518 // to the fetch stage is sent to squash history after the mispredict 519 520 History &pred_hist = predHist[tid]; 521 522 ++condIncorrect; 523 ppMisses->notify(1); 524 525 DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, " 526 "setting target to %s.\n", tid, squashed_sn, corrTarget); 527 528 // Squash All Branches AFTER this mispredicted branch 529 squash(squashed_sn, tid); 530 531 // If there's a squash due to a syscall, there may not be an entry 532 // corresponding to the squash. In that case, don't bother trying to 533 // fix up the entry. 534 if (!pred_hist.empty()) { 535 536 auto hist_it = pred_hist.begin(); 537 //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(), 538 // squashed_sn); 539 540 //assert(hist_it != pred_hist.end()); 541 if (pred_hist.front().seqNum != squashed_sn) { 542 DPRINTF(Branch, "Front sn %i != Squash sn %i\n", 543 pred_hist.front().seqNum, squashed_sn); 544 545 assert(pred_hist.front().seqNum == squashed_sn); 546 } 547 548 549 if ((*hist_it).usedRAS) { 550 ++RASIncorrect; 551 DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n", 552 tid, hist_it->seqNum); 553 } 554 555 // Have to get GHR here because the update deletes bpHistory 556 unsigned ghr = getGHR(tid, hist_it->bpHistory); 557 558 update(tid, (*hist_it).pc, actually_taken, 559 pred_hist.front().bpHistory, true); 560 hist_it->wasSquashed = true; 561 562 if (actually_taken) { 563 if (hist_it->wasReturn && !hist_it->usedRAS) { 564 DPRINTF(Branch, "[tid: %i] Incorrectly predicted" 565 " return [sn:%i] PC: %s\n", tid, hist_it->seqNum, 566 hist_it->pc); 567 RAS[tid].pop(); 568 hist_it->usedRAS = true; 569 } 570 if (hist_it->wasIndirect) { 571 ++indirectMispredicted; 572 iPred.recordTarget(hist_it->seqNum, ghr, corrTarget, tid); 573 } else { 574 DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]" 575 " PC: %s\n", tid,hist_it->seqNum, hist_it->pc); 576 577 BTB.update((*hist_it).pc, corrTarget, tid); 578 } 579 } else { 580 //Actually not Taken 581 if (hist_it->usedRAS) { 582 DPRINTF(Branch,"[tid: %i] Incorrectly predicted" 583 " return [sn:%i] PC: %s Restoring RAS\n", tid, 584 hist_it->seqNum, hist_it->pc); 585 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS" 586 " to: %i, target: %s.\n", tid, 587 hist_it->RASIndex, hist_it->RASTarget); 588 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget); 589 hist_it->usedRAS = false; 590 } else if (hist_it->wasCall && hist_it->pushedRAS) { 591 //Was a Call but predicated false. Pop RAS here 592 DPRINTF(Branch, "[tid: %i] Incorrectly predicted" 593 " Call [sn:%i] PC: %s Popping RAS\n", tid, 594 hist_it->seqNum, hist_it->pc); 595 RAS[tid].pop(); 596 hist_it->pushedRAS = false; 597 } 598 } 599 } else { 600 DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't " 601 "update.\n", tid, squashed_sn); 602 } 603} 604 605void 606BPredUnit::dump() 607{ 608 int i = 0; 609 for (const auto& ph : predHist) { 610 if (!ph.empty()) { 611 auto pred_hist_it = ph.begin(); 612 613 cprintf("predHist[%i].size(): %i\n", i++, ph.size()); 614 615 while (pred_hist_it != ph.end()) { 616 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, " 617 "bpHistory:%#x\n", 618 pred_hist_it->seqNum, pred_hist_it->pc, 619 pred_hist_it->tid, pred_hist_it->predTaken, 620 pred_hist_it->bpHistory); 621 pred_hist_it++; 622 } 623 624 cprintf("\n"); 625 } 626 } 627} 628 629