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]: 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()) {

--- 6 unchanged lines hidden (view full) ---

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 }

--- 17 unchanged lines hidden (view full) ---

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,

--- 14 unchanged lines hidden (view full) ---

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{

--- 8 unchanged lines hidden (view full) ---

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()) {

--- 8 unchanged lines hidden (view full) ---

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

--- 10 unchanged lines hidden (view full) ---

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