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