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