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