bpred_unit.cc revision 13810:f50e3b82df73
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]: Unconditional control.\n", tid); 200 pred_taken = true; 201 // Tell the BP there was an unconditional branch. 202 uncondBranch(tid, pc.instAddr(), bp_history); 203 } else { 204 ++condPredicted; 205 pred_taken = lookup(tid, pc.instAddr(), bp_history); 206 207 DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor" 208 " predicted %i for PC %s\n", tid, seqNum, pred_taken, pc); 209 } 210 211 const bool orig_pred_taken = pred_taken; 212 if (useIndirect) { 213 iPred.genIndirectInfo(tid, indirect_history); 214 } 215 216 DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history " 217 "for PC %s\n", tid, seqNum, pc); 218 219 PredictorHistory predict_record(seqNum, pc.instAddr(), pred_taken, 220 bp_history, indirect_history, tid, inst); 221 222 // Now lookup in the BTB or RAS. 223 if (pred_taken) { 224 if (inst->isReturn()) { 225 ++usedRAS; 226 predict_record.wasReturn = true; 227 // If it's a function return call, then look up the address 228 // in the RAS. 229 TheISA::PCState rasTop = RAS[tid].top(); 230 target = TheISA::buildRetPC(pc, rasTop); 231 232 // Record the top entry of the RAS, and its index. 233 predict_record.usedRAS = true; 234 predict_record.RASIndex = RAS[tid].topIdx(); 235 predict_record.RASTarget = rasTop; 236 237 RAS[tid].pop(); 238 239 DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, " 240 "RAS predicted target: %s, RAS index: %i.\n", 241 tid, pc, target, predict_record.RASIndex); 242 } else { 243 ++BTBLookups; 244 245 if (inst->isCall()) { 246 RAS[tid].push(pc); 247 predict_record.pushedRAS = true; 248 249 // Record that it was a call so that the top RAS entry can 250 // be popped off if the speculation is incorrect. 251 predict_record.wasCall = true; 252 253 DPRINTF(Branch, "[tid:%i]: Instruction %s was a " 254 "call, adding %s to the RAS index: %i.\n", 255 tid, pc, pc, RAS[tid].topIdx()); 256 } 257 258 if (inst->isDirectCtrl() || !useIndirect) { 259 // Check BTB on direct branches 260 if (BTB.valid(pc.instAddr(), tid)) { 261 ++BTBHits; 262 263 // If it's not a return, use the BTB to get target addr. 264 target = BTB.lookup(pc.instAddr(), tid); 265 266 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted" 267 " target is %s.\n", tid, pc, target); 268 269 } else { 270 DPRINTF(Branch, "[tid:%i]: BTB doesn't have a " 271 "valid entry.\n",tid); 272 pred_taken = false; 273 // The Direction of the branch predictor is altered 274 // because the BTB did not have an entry 275 // The predictor needs to be updated accordingly 276 if (!inst->isCall() && !inst->isReturn()) { 277 btbUpdate(tid, pc.instAddr(), bp_history); 278 DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate" 279 " called for %s\n", tid, seqNum, pc); 280 } else if (inst->isCall() && !inst->isUncondCtrl()) { 281 RAS[tid].pop(); 282 predict_record.pushedRAS = false; 283 } 284 TheISA::advancePC(target, inst); 285 } 286 } else { 287 predict_record.wasIndirect = true; 288 ++indirectLookups; 289 //Consult indirect predictor on indirect control 290 if (iPred.lookup(pc.instAddr(), target, tid)) { 291 // Indirect predictor hit 292 ++indirectHits; 293 DPRINTF(Branch, "[tid:%i]: Instruction %s predicted " 294 "indirect target is %s.\n", tid, pc, target); 295 } else { 296 ++indirectMisses; 297 pred_taken = false; 298 DPRINTF(Branch, "[tid:%i]: Instruction %s no indirect " 299 "target.\n", tid, pc); 300 if (!inst->isCall() && !inst->isReturn()) { 301 302 } else if (inst->isCall() && !inst->isUncondCtrl()) { 303 RAS[tid].pop(); 304 predict_record.pushedRAS = false; 305 } 306 TheISA::advancePC(target, inst); 307 } 308 iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum, 309 tid); 310 } 311 } 312 } else { 313 if (inst->isReturn()) { 314 predict_record.wasReturn = true; 315 } 316 TheISA::advancePC(target, inst); 317 } 318 predict_record.target = target.instAddr(); 319 320 pc = target; 321 322 if (useIndirect) { 323 // Update the indirect predictor with the direction prediction 324 // Note that this happens after indirect lookup, so it does not use 325 // the new information 326 // Note also that we use orig_pred_taken instead of pred_taken in 327 // as this is the actual outcome of the direction prediction 328 iPred.updateDirectionInfo(tid, orig_pred_taken); 329 } 330 331 predHist[tid].push_front(predict_record); 332 333 DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added." 334 "predHist.size(): %i\n", tid, seqNum, predHist[tid].size()); 335 336 return pred_taken; 337} 338 339void 340BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid) 341{ 342 DPRINTF(Branch, "[tid:%i]: Committing branches until " 343 "[sn:%lli].\n", tid, done_sn); 344 345 while (!predHist[tid].empty() && 346 predHist[tid].back().seqNum <= done_sn) { 347 // Update the branch predictor with the correct results. 348 update(tid, predHist[tid].back().pc, 349 predHist[tid].back().predTaken, 350 predHist[tid].back().bpHistory, false, 351 predHist[tid].back().inst, 352 predHist[tid].back().target); 353 354 if (useIndirect) { 355 iPred.commit(done_sn, tid, predHist[tid].back().indirectHistory); 356 } 357 358 predHist[tid].pop_back(); 359 } 360} 361 362void 363BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid) 364{ 365 History &pred_hist = predHist[tid]; 366 367 if (useIndirect) { 368 iPred.squash(squashed_sn, tid); 369 } 370 371 while (!pred_hist.empty() && 372 pred_hist.front().seqNum > squashed_sn) { 373 if (pred_hist.front().usedRAS) { 374 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i," 375 " target: %s.\n", tid, 376 pred_hist.front().RASIndex, pred_hist.front().RASTarget); 377 378 RAS[tid].restore(pred_hist.front().RASIndex, 379 pred_hist.front().RASTarget); 380 } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) { 381 // Was a call but predicated false. Pop RAS here 382 DPRINTF(Branch, "[tid: %i] Squashing" 383 " Call [sn:%i] PC: %s Popping RAS\n", tid, 384 pred_hist.front().seqNum, pred_hist.front().pc); 385 RAS[tid].pop(); 386 } 387 388 // This call should delete the bpHistory. 389 squash(tid, pred_hist.front().bpHistory); 390 if (useIndirect) { 391 iPred.deleteIndirectInfo(tid, pred_hist.front().indirectHistory); 392 } 393 394 DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] " 395 "PC %s.\n", tid, pred_hist.front().seqNum, 396 pred_hist.front().pc); 397 398 pred_hist.pop_front(); 399 400 DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n", 401 tid, predHist[tid].size()); 402 } 403} 404 405void 406BPredUnit::squash(const InstSeqNum &squashed_sn, 407 const TheISA::PCState &corrTarget, 408 bool actually_taken, ThreadID tid) 409{ 410 // Now that we know that a branch was mispredicted, we need to undo 411 // all the branches that have been seen up until this branch and 412 // fix up everything. 413 // NOTE: This should be call conceivably in 2 scenarios: 414 // (1) After an branch is executed, it updates its status in the ROB 415 // The commit stage then checks the ROB update and sends a signal to 416 // the fetch stage to squash history after the mispredict 417 // (2) In the decode stage, you can find out early if a unconditional 418 // PC-relative, branch was predicted incorrectly. If so, a signal 419 // to the fetch stage is sent to squash history after the mispredict 420 421 History &pred_hist = predHist[tid]; 422 423 ++condIncorrect; 424 ppMisses->notify(1); 425 426 DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, " 427 "setting target to %s.\n", tid, squashed_sn, corrTarget); 428 429 // Squash All Branches AFTER this mispredicted branch 430 squash(squashed_sn, tid); 431 432 // If there's a squash due to a syscall, there may not be an entry 433 // corresponding to the squash. In that case, don't bother trying to 434 // fix up the entry. 435 if (!pred_hist.empty()) { 436 437 auto hist_it = pred_hist.begin(); 438 //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(), 439 // squashed_sn); 440 441 //assert(hist_it != pred_hist.end()); 442 if (pred_hist.front().seqNum != squashed_sn) { 443 DPRINTF(Branch, "Front sn %i != Squash sn %i\n", 444 pred_hist.front().seqNum, squashed_sn); 445 446 assert(pred_hist.front().seqNum == squashed_sn); 447 } 448 449 450 if ((*hist_it).usedRAS) { 451 ++RASIncorrect; 452 DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n", 453 tid, hist_it->seqNum); 454 } 455 456 // There are separate functions for in-order and out-of-order 457 // branch prediction, but not for update. Therefore, this 458 // call should take into account that the mispredicted branch may 459 // be on the wrong path (i.e., OoO execution), and that the counter 460 // counter table(s) should not be updated. Thus, this call should 461 // restore the state of the underlying predictor, for instance the 462 // local/global histories. The counter tables will be updated when 463 // the branch actually commits. 464 465 // Remember the correct direction for the update at commit. 466 pred_hist.front().predTaken = actually_taken; 467 pred_hist.front().target = corrTarget.instAddr(); 468 469 update(tid, (*hist_it).pc, actually_taken, 470 pred_hist.front().bpHistory, true, pred_hist.front().inst, 471 corrTarget.instAddr()); 472 473 if (useIndirect) { 474 iPred.changeDirectionPrediction(tid, 475 pred_hist.front().indirectHistory, actually_taken); 476 } 477 478 if (actually_taken) { 479 if (hist_it->wasReturn && !hist_it->usedRAS) { 480 DPRINTF(Branch, "[tid: %i] Incorrectly predicted" 481 " return [sn:%i] PC: %s\n", tid, hist_it->seqNum, 482 hist_it->pc); 483 RAS[tid].pop(); 484 hist_it->usedRAS = true; 485 } 486 if (hist_it->wasIndirect) { 487 ++indirectMispredicted; 488 iPred.recordTarget( 489 hist_it->seqNum, pred_hist.front().indirectHistory, 490 corrTarget, tid); 491 } else { 492 DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]" 493 " PC: %s\n", tid,hist_it->seqNum, hist_it->pc); 494 495 BTB.update((*hist_it).pc, corrTarget, tid); 496 } 497 } else { 498 //Actually not Taken 499 if (hist_it->usedRAS) { 500 DPRINTF(Branch,"[tid: %i] Incorrectly predicted" 501 " return [sn:%i] PC: %s Restoring RAS\n", tid, 502 hist_it->seqNum, hist_it->pc); 503 DPRINTF(Branch, "[tid:%i]: Restoring top of RAS" 504 " to: %i, target: %s.\n", tid, 505 hist_it->RASIndex, hist_it->RASTarget); 506 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget); 507 hist_it->usedRAS = false; 508 } else if (hist_it->wasCall && hist_it->pushedRAS) { 509 //Was a Call but predicated false. Pop RAS here 510 DPRINTF(Branch, "[tid: %i] Incorrectly predicted" 511 " Call [sn:%i] PC: %s Popping RAS\n", tid, 512 hist_it->seqNum, hist_it->pc); 513 RAS[tid].pop(); 514 hist_it->pushedRAS = false; 515 } 516 } 517 } else { 518 DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't " 519 "update.\n", tid, squashed_sn); 520 } 521} 522 523void 524BPredUnit::dump() 525{ 526 int i = 0; 527 for (const auto& ph : predHist) { 528 if (!ph.empty()) { 529 auto pred_hist_it = ph.begin(); 530 531 cprintf("predHist[%i].size(): %i\n", i++, ph.size()); 532 533 while (pred_hist_it != ph.end()) { 534 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, " 535 "bpHistory:%#x\n", 536 pred_hist_it->seqNum, pred_hist_it->pc, 537 pred_hist_it->tid, pred_hist_it->predTaken, 538 pred_hist_it->bpHistory); 539 pred_hist_it++; 540 } 541 542 cprintf("\n"); 543 } 544 } 545} 546 547