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 --- 182 unchanged lines hidden (view full) --- 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()) { --- 6 unchanged lines hidden (view full) --- 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 } --- 17 unchanged lines hidden (view full) --- 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, --- 14 unchanged lines hidden (view full) --- 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{ --- 8 unchanged lines hidden (view full) --- 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()) { --- 8 unchanged lines hidden (view full) --- 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 --- 10 unchanged lines hidden (view full) --- 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 |