bpred_unit.cc revision 11434:b5aed9d2d54e
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 lookups 84 .name(name() + ".lookups") 85 .desc("Number of BP lookups") 86 ; 87 88 condPredicted 89 .name(name() + ".condPredicted") 90 .desc("Number of conditional branches predicted") 91 ; 92 93 condIncorrect 94 .name(name() + ".condIncorrect") 95 .desc("Number of conditional branches incorrect") 96 ; 97 98 BTBLookups 99 .name(name() + ".BTBLookups") 100 .desc("Number of BTB lookups") 101 ; 102 103 BTBHits 104 .name(name() + ".BTBHits") 105 .desc("Number of BTB hits") 106 ; 107 108 BTBCorrect 109 .name(name() + ".BTBCorrect") 110 .desc("Number of correct BTB predictions (this stat may not " 111 "work properly.") 112 ; 113 114 BTBHitPct 115 .name(name() + ".BTBHitPct") 116 .desc("BTB Hit Percentage") 117 .precision(6); 118 BTBHitPct = (BTBHits / BTBLookups) * 100; 119 120 usedRAS 121 .name(name() + ".usedRAS") 122 .desc("Number of times the RAS was used to get a target.") 123 ; 124 125 RASIncorrect 126 .name(name() + ".RASInCorrect") 127 .desc("Number of incorrect RAS predictions.") 128 ; 129 130 indirectLookups 131 .name(name() + ".indirectLookups") 132 .desc("Number of indirect predictor lookups.") 133 ; 134 135 indirectHits 136 .name(name() + ".indirectHits") 137 .desc("Number of indirect target hits.") 138 ; 139 140 indirectMisses 141 .name(name() + ".indirectMisses") 142 .desc("Number of indirect misses.") 143 ; 144 145 indirectMispredicted 146 .name(name() + "indirectMispredicted") 147 .desc("Number of mispredicted indirect branches.") 148 ; 149 150} 151 152ProbePoints::PMUUPtr 153BPredUnit::pmuProbePoint(const char *name) 154{ 155 ProbePoints::PMUUPtr ptr; 156 ptr.reset(new ProbePoints::PMU(getProbeManager(), name)); 157 158 return ptr; 159} 160 161void 162BPredUnit::regProbePoints() 163{ 164 ppBranches = pmuProbePoint("Branches"); 165 ppMisses = pmuProbePoint("Misses"); 166} 167 168void 169BPredUnit::drainSanityCheck() const 170{ 171 // We shouldn't have any outstanding requests when we resume from 172 // a drained system. 173 for (const auto& ph M5_VAR_USED : predHist) 174 assert(ph.empty()); 175} 176 177bool 178BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum, 179 TheISA::PCState &pc, ThreadID tid) 180{ 181 // See if branch predictor predicts taken. 182 // If so, get its target addr either from the BTB or the RAS. 183 // Save off record of branch stuff so the RAS can be fixed 184 // up once it's done. 185 186 bool pred_taken = false; 187 TheISA::PCState target = pc; 188 189 ++lookups; 190 ppBranches->notify(1); 191 192 void *bp_history = NULL; 193 194 if (inst->isUncondCtrl()) { 195 DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid); 196 pred_taken = true; 197 // Tell the BP there was an unconditional branch. 198 uncondBranch(tid, pc.instAddr(), bp_history); 199 } else { 200 ++condPredicted; 201 pred_taken = lookup(tid, pc.instAddr(), bp_history); 202 203 DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor" 204 " predicted %i for PC %s\n", tid, seqNum, pred_taken, pc); 205 } 206 207 DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history " 208 "for PC %s\n", tid, seqNum, pc); 209 210 PredictorHistory predict_record(seqNum, pc.instAddr(), 211 pred_taken, bp_history, tid); 212 213 // Now lookup in the BTB or RAS. 214 if (pred_taken) { 215 if (inst->isReturn()) { 216 ++usedRAS; 217 predict_record.wasReturn = true; 218 // If it's a function return call, then look up the address 219 // in the RAS. 220 TheISA::PCState rasTop = RAS[tid].top(); 221 target = TheISA::buildRetPC(pc, rasTop); 222 223 // Record the top entry of the RAS, and its index. 224 predict_record.usedRAS = true; 225 predict_record.RASIndex = RAS[tid].topIdx(); 226 predict_record.RASTarget = rasTop; 227 228 RAS[tid].pop(); 229 230 DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, " 231 "RAS predicted target: %s, RAS index: %i.\n", 232 tid, pc, target, predict_record.RASIndex); 233 } else { 234 ++BTBLookups; 235 236 if (inst->isCall()) { 237 RAS[tid].push(pc); 238 predict_record.pushedRAS = true; 239 240 // Record that it was a call so that the top RAS entry can 241 // be popped off if the speculation is incorrect. 242 predict_record.wasCall = true; 243 244 DPRINTF(Branch, "[tid:%i]: Instruction %s was a " 245 "call, adding %s to the RAS index: %i.\n", 246 tid, pc, pc, RAS[tid].topIdx()); 247 } 248 249 if (inst->isDirectCtrl() || !useIndirect) { 250 // Check BTB on direct branches 251 if (BTB.valid(pc.instAddr(), tid)) { 252 ++BTBHits; 253 254 // If it's not a return, use the BTB to get target addr. 255 target = BTB.lookup(pc.instAddr(), tid); 256 257 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted" 258 " target is %s.\n", tid, pc, target); 259 260 } else { 261 DPRINTF(Branch, "[tid:%i]: BTB doesn't have a " 262 "valid entry.\n",tid); 263 pred_taken = false; 264 // The Direction of the branch predictor is altered 265 // because the BTB did not have an entry 266 // The predictor needs to be updated accordingly 267 if (!inst->isCall() && !inst->isReturn()) { 268 btbUpdate(tid, pc.instAddr(), bp_history); 269 DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate" 270 " called for %s\n", tid, seqNum, pc); 271 } else if (inst->isCall() && !inst->isUncondCtrl()) { 272 RAS[tid].pop(); 273 predict_record.pushedRAS = false; 274 } 275 TheISA::advancePC(target, inst); 276 } 277 } else { 278 predict_record.wasIndirect = true; 279 ++indirectLookups; 280 //Consult indirect predictor on indirect control 281 if (iPred.lookup(pc.instAddr(), getGHR(tid, bp_history), 282 target, tid)) { 283 // Indirect predictor hit 284 ++indirectHits; 285 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted " 286 "indirect target is %s.\n", tid, pc, target); 287 } else { 288 ++indirectMisses; 289 pred_taken = false; 290 DPRINTF(Branch, "[tid:%i]: Instruction %s no indirect " 291 "target.\n", tid, pc); 292 if (!inst->isCall() && !inst->isReturn()) { 293 294 } else if (inst->isCall() && !inst->isUncondCtrl()) { 295 RAS[tid].pop(); 296 predict_record.pushedRAS = false; 297 } 298 TheISA::advancePC(target, inst); 299 } 300 iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum, 301 tid); 302 } 303 } 304 } else { 305 if (inst->isReturn()) { 306 predict_record.wasReturn = true; 307 } 308 TheISA::advancePC(target, inst); 309 } 310 311 pc = target; 312 313 predHist[tid].push_front(predict_record); 314 315 DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added." 316 "predHist.size(): %i\n", tid, seqNum, predHist[tid].size()); 317 318 return pred_taken; 319} 320 321bool 322BPredUnit::predictInOrder(const StaticInstPtr &inst, const InstSeqNum &seqNum, 323 int asid, TheISA::PCState &instPC, 324 TheISA::PCState &predPC, ThreadID tid) 325{ 326 // See if branch predictor predicts taken. 327 // If so, get its target addr either from the BTB or the RAS. 328 // Save off record of branch stuff so the RAS can be fixed 329 // up once it's done. 330 331 using TheISA::MachInst; 332 333 bool pred_taken = false; 334 TheISA::PCState target; 335 336 ++lookups; 337 ppBranches->notify(1); 338 339 DPRINTF(Branch, "[tid:%i] [sn:%i] %s ... PC %s doing branch " 340 "prediction\n", tid, seqNum, 341 inst->disassemble(instPC.instAddr()), instPC); 342 343 void *bp_history = NULL; 344 345 if (inst->isUncondCtrl()) { 346 DPRINTF(Branch, "[tid:%i] Unconditional control.\n", tid); 347 pred_taken = true; 348 // Tell the BP there was an unconditional branch. 349 uncondBranch(tid, instPC.instAddr(), bp_history); 350 351 if (inst->isReturn() && RAS[tid].empty()) { 352 DPRINTF(Branch, "[tid:%i] RAS is empty, predicting " 353 "false.\n", tid); 354 pred_taken = false; 355 } 356 } else { 357 ++condPredicted; 358 359 pred_taken = lookup(tid, predPC.instAddr(), bp_history); 360 } 361 362 PredictorHistory predict_record(seqNum, predPC.instAddr(), pred_taken, 363 bp_history, tid); 364 365 // Now lookup in the BTB or RAS. 366 if (pred_taken) { 367 if (inst->isReturn()) { 368 ++usedRAS; 369 370 // If it's a function return call, then look up the address 371 // in the RAS. 372 TheISA::PCState rasTop = RAS[tid].top(); 373 target = TheISA::buildRetPC(instPC, rasTop); 374 375 // Record the top entry of the RAS, and its index. 376 predict_record.usedRAS = true; 377 predict_record.RASIndex = RAS[tid].topIdx(); 378 predict_record.RASTarget = rasTop; 379 380 assert(predict_record.RASIndex < 16); 381 382 RAS[tid].pop(); 383 384 DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, " 385 "RAS predicted target: %s, RAS index: %i.\n", 386 tid, instPC, target, 387 predict_record.RASIndex); 388 } else { 389 ++BTBLookups; 390 391 if (inst->isCall()) { 392 393 RAS[tid].push(instPC); 394 predict_record.pushedRAS = true; 395 396 // Record that it was a call so that the top RAS entry can 397 // be popped off if the speculation is incorrect. 398 predict_record.wasCall = true; 399 400 DPRINTF(Branch, "[tid:%i]: Instruction %s was a call" 401 ", adding %s to the RAS index: %i.\n", 402 tid, instPC, predPC, 403 RAS[tid].topIdx()); 404 } 405 406 if (inst->isCall() && 407 inst->isUncondCtrl() && 408 inst->isDirectCtrl()) { 409 target = inst->branchTarget(instPC); 410 } else if (BTB.valid(predPC.instAddr(), asid)) { 411 ++BTBHits; 412 413 // If it's not a return, use the BTB to get the target addr. 414 target = BTB.lookup(predPC.instAddr(), asid); 415 416 DPRINTF(Branch, "[tid:%i]: [asid:%i] Instruction %s " 417 "predicted target is %s.\n", 418 tid, asid, instPC, target); 419 } else { 420 DPRINTF(Branch, "[tid:%i]: BTB doesn't have a " 421 "valid entry, predicting false.\n",tid); 422 pred_taken = false; 423 } 424 } 425 } 426 427 if (pred_taken) { 428 // Set the PC and the instruction's predicted target. 429 predPC = target; 430 } 431 DPRINTF(Branch, "[tid:%i]: [sn:%i]: Setting Predicted PC to %s.\n", 432 tid, seqNum, predPC); 433 434 predHist[tid].push_front(predict_record); 435 436 DPRINTF(Branch, "[tid:%i] [sn:%i] pushed onto front of predHist " 437 "...predHist.size(): %i\n", 438 tid, seqNum, predHist[tid].size()); 439 440 return pred_taken; 441} 442 443void 444BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid) 445{ 446 DPRINTF(Branch, "[tid:%i]: Committing branches until " 447 "[sn:%lli].\n", tid, done_sn); 448 449 iPred.commit(done_sn, tid); 450 while (!predHist[tid].empty() && 451 predHist[tid].back().seqNum <= done_sn) { 452 // Update the branch predictor with the correct results. 453 if (!predHist[tid].back().wasSquashed) { 454 update(tid, predHist[tid].back().pc, 455 predHist[tid].back().predTaken, 456 predHist[tid].back().bpHistory, false); 457 } else { 458 retireSquashed(tid, predHist[tid].back().bpHistory); 459 } 460 461 predHist[tid].pop_back(); 462 } 463} 464 465void 466BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) 467{ 468 History &pred_hist = predHist[tid]; 469 470 iPred.squash(squashed_sn, tid); 471 while (!pred_hist.empty() && 472 pred_hist.front().seqNum > squashed_sn) { 473 if (pred_hist.front().usedRAS) { 474 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i," 475 " target: %s.\n", tid, 476 pred_hist.front().RASIndex, pred_hist.front().RASTarget); 477 478 RAS[tid].restore(pred_hist.front().RASIndex, 479 pred_hist.front().RASTarget); 480 } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) { 481 // Was a call but predicated false. Pop RAS here 482 DPRINTF(Branch, "[tid: %i] Squashing" 483 " Call [sn:%i] PC: %s Popping RAS\n", tid, 484 pred_hist.front().seqNum, pred_hist.front().pc); 485 RAS[tid].pop(); 486 } 487 488 // This call should delete the bpHistory. 489 squash(tid, pred_hist.front().bpHistory); 490 491 DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] " 492 "PC %s.\n", tid, pred_hist.front().seqNum, 493 pred_hist.front().pc); 494 495 pred_hist.pop_front(); 496 497 DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n", 498 tid, predHist[tid].size()); 499 } 500} 501 502void 503BPredUnit::squash(const InstSeqNum &squashed_sn, 504 const TheISA::PCState &corrTarget, 505 bool actually_taken, ThreadID tid) 506{ 507 // Now that we know that a branch was mispredicted, we need to undo 508 // all the branches that have been seen up until this branch and 509 // fix up everything. 510 // NOTE: This should be call conceivably in 2 scenarios: 511 // (1) After an branch is executed, it updates its status in the ROB 512 // The commit stage then checks the ROB update and sends a signal to 513 // the fetch stage to squash history after the mispredict 514 // (2) In the decode stage, you can find out early if a unconditional 515 // PC-relative, branch was predicted incorrectly. If so, a signal 516 // to the fetch stage is sent to squash history after the mispredict 517 518 History &pred_hist = predHist[tid]; 519 520 ++condIncorrect; 521 ppMisses->notify(1); 522 523 DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, " 524 "setting target to %s.\n", tid, squashed_sn, corrTarget); 525 526 // Squash All Branches AFTER this mispredicted branch 527 squash(squashed_sn, tid); 528 529 // If there's a squash due to a syscall, there may not be an entry 530 // corresponding to the squash. In that case, don't bother trying to 531 // fix up the entry. 532 if (!pred_hist.empty()) { 533 534 auto hist_it = pred_hist.begin(); 535 //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(), 536 // squashed_sn); 537 538 //assert(hist_it != pred_hist.end()); 539 if (pred_hist.front().seqNum != squashed_sn) { 540 DPRINTF(Branch, "Front sn %i != Squash sn %i\n", 541 pred_hist.front().seqNum, squashed_sn); 542 543 assert(pred_hist.front().seqNum == squashed_sn); 544 } 545 546 547 if ((*hist_it).usedRAS) { 548 ++RASIncorrect; 549 DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n", 550 tid, hist_it->seqNum); 551 } 552 553 // Have to get GHR here because the update deletes bpHistory 554 unsigned ghr = getGHR(tid, hist_it->bpHistory); 555 556 update(tid, (*hist_it).pc, actually_taken, 557 pred_hist.front().bpHistory, true); 558 hist_it->wasSquashed = true; 559 560 if (actually_taken) { 561 if (hist_it->wasReturn && !hist_it->usedRAS) { 562 DPRINTF(Branch, "[tid: %i] Incorrectly predicted" 563 " return [sn:%i] PC: %s\n", tid, hist_it->seqNum, 564 hist_it->pc); 565 RAS[tid].pop(); 566 hist_it->usedRAS = true; 567 } 568 if (hist_it->wasIndirect) { 569 ++indirectMispredicted; 570 iPred.recordTarget(hist_it->seqNum, ghr, corrTarget, tid); 571 } else { 572 DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]" 573 " PC: %s\n", tid,hist_it->seqNum, hist_it->pc); 574 575 BTB.update((*hist_it).pc, corrTarget, tid); 576 } 577 } else { 578 //Actually not Taken 579 if (hist_it->usedRAS) { 580 DPRINTF(Branch,"[tid: %i] Incorrectly predicted" 581 " return [sn:%i] PC: %s Restoring RAS\n", tid, 582 hist_it->seqNum, hist_it->pc); 583 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS" 584 " to: %i, target: %s.\n", tid, 585 hist_it->RASIndex, hist_it->RASTarget); 586 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget); 587 hist_it->usedRAS = false; 588 } else if (hist_it->wasCall && hist_it->pushedRAS) { 589 //Was a Call but predicated false. Pop RAS here 590 DPRINTF(Branch, "[tid: %i] Incorrectly predicted" 591 " Call [sn:%i] PC: %s Popping RAS\n", tid, 592 hist_it->seqNum, hist_it->pc); 593 RAS[tid].pop(); 594 hist_it->pushedRAS = false; 595 } 596 } 597 } else { 598 DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't " 599 "update.\n", tid, squashed_sn); 600 } 601} 602 603void 604BPredUnit::dump() 605{ 606 int i = 0; 607 for (const auto& ph : predHist) { 608 if (!ph.empty()) { 609 auto pred_hist_it = ph.begin(); 610 611 cprintf("predHist[%i].size(): %i\n", i++, ph.size()); 612 613 while (pred_hist_it != ph.end()) { 614 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, " 615 "bpHistory:%#x\n", 616 pred_hist_it->seqNum, pred_hist_it->pc, 617 pred_hist_it->tid, pred_hist_it->predTaken, 618 pred_hist_it->bpHistory); 619 pred_hist_it++; 620 } 621 622 cprintf("\n"); 623 } 624 } 625} 626 627