src/cpu/pred/bpred_unit.cc

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