src/cpu/o3/bpred_unit_impl.hh

   1 /*
   2  * Copyright (c) 2011 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Copyright (c) 2004-2005 The Regents of The University of Michigan
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions are
  19  * met: redistributions of source code must retain the above copyright
  20  * notice, this list of conditions and the following disclaimer;
  21  * redistributions in binary form must reproduce the above copyright
  22  * notice, this list of conditions and the following disclaimer in the
  23  * documentation and/or other materials provided with the distribution;
  24  * neither the name of the copyright holders nor the names of its
  25  * contributors may be used to endorse or promote products derived from
  26  * this software without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39  *
  40  * Authors: Kevin Lim
  41  */
  42
  43 #include <algorithm>
  44
  45 #include "arch/isa_traits.hh"
  46 #include "arch/types.hh"
  47 #include "arch/utility.hh"
  48 #include "base/trace.hh"
  49 #include "config/the_isa.hh"
  50 #include "cpu/o3/bpred_unit.hh"
  51 #include "debug/Fetch.hh"
  52 #include "params/DerivO3CPU.hh"
  53
  54 template<class Impl>
  55 BPredUnit<Impl>::BPredUnit(DerivO3CPUParams *params)
  56     : _name(params->name + ".BPredUnit"),
  57       BTB(params->BTBEntries,
  58           params->BTBTagSize,
  59           params->instShiftAmt)
  60 {
  61     // Setup the selected predictor.
  62     if (params->predType == "local") {
  63         localBP = new LocalBP(params->localPredictorSize,
  64                               params->localCtrBits,
  65                               params->instShiftAmt);
  66         predictor = Local;
  67     } else if (params->predType == "tournament") {
  68         tournamentBP = new TournamentBP(params->localPredictorSize,
  69                                         params->localCtrBits,
  70                                         params->localHistoryTableSize,
  71                                         params->localHistoryBits,
  72                                         params->globalPredictorSize,
  73                                         params->globalHistoryBits,
  74                                         params->globalCtrBits,
  75                                         params->choicePredictorSize,
  76                                         params->choiceCtrBits,
  77                                         params->instShiftAmt);
  78         predictor = Tournament;
  79     } else {
  80         fatal("Invalid BP selected!");
  81     }
  82
  83     for (int i=0; i < Impl::MaxThreads; i++)
  84         RAS[i].init(params->RASSize);
  85 }
  86
  87 template <class Impl>
  88 void
  89 BPredUnit<Impl>::regStats()
  90 {
  91     lookups
  92         .name(name() + ".lookups")
  93         .desc("Number of BP lookups")
  94         ;
  95
  96     condPredicted
  97         .name(name() + ".condPredicted")
  98         .desc("Number of conditional branches predicted")
  99         ;
 100
 101     condIncorrect
 102         .name(name() + ".condIncorrect")
 103         .desc("Number of conditional branches incorrect")
 104         ;
 105
 106     BTBLookups
 107         .name(name() + ".BTBLookups")
 108         .desc("Number of BTB lookups")
 109         ;
 110
 111     BTBHits
 112         .name(name() + ".BTBHits")
 113         .desc("Number of BTB hits")
 114         ;
 115
 116     BTBCorrect
 117         .name(name() + ".BTBCorrect")
 118         .desc("Number of correct BTB predictions (this stat may not "
 119               "work properly.")
 120         ;
 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
 133 template <class Impl>
 134 void
 135 BPredUnit<Impl>::switchOut()
 136 {
 137     // Clear any state upon switch out.
 138     for (int i = 0; i < Impl::MaxThreads; ++i) {
 139         squash(0, i);
 140     }
 141 }
 142
 143 template <class Impl>
 144 void
 145 BPredUnit<Impl>::takeOverFrom()
 146 {
 147     // Can reset all predictor state, but it's not necessarily better
 148     // than leaving it be.
 149 /*
 150     for (int i = 0; i < Impl::MaxThreads; ++i)
 151         RAS[i].reset();
 152
 153     BP.reset();
 154     BTB.reset();
 155 */
 156 }
 157
 158 template <class Impl>
 159 bool
 160 BPredUnit<Impl>::predict(DynInstPtr &inst, TheISA::PCState &pc, ThreadID tid)
 161 {
 162     // See if branch predictor predicts taken.
 163     // If so, get its target addr either from the BTB or the RAS.
 164     // Save off record of branch stuff so the RAS can be fixed
 165     // up once it's done.
 166
 167     bool pred_taken = false;
 168     TheISA::PCState target = pc;
 169
 170     ++lookups;
 171
 172     void *bp_history = NULL;
 173
 174     if (inst->isUncondCtrl()) {
 175         DPRINTF(Fetch, "BranchPred: [tid:%i]: Unconditional control.\n", tid);
 176         pred_taken = true;
 177         // Tell the BP there was an unconditional branch.
 178         BPUncond(bp_history);
 179     } else {
 180         ++condPredicted;
 181         pred_taken = BPLookup(pc.instAddr(), bp_history);
 182
 183         DPRINTF(Fetch, "BranchPred:[tid:%i]: [sn:%i] Branch predictor"
 184                 " predicted %i for PC %s\n",
 185                 tid, inst->seqNum,  pred_taken, inst->pcState());
 186     }
 187
 188     DPRINTF(Fetch, "BranchPred: [tid:%i]: [sn:%i] Creating prediction history "
 189                 "for PC %s\n",
 190             tid, inst->seqNum, inst->pcState());
 191
 192     PredictorHistory predict_record(inst->seqNum, pc.instAddr(),
 193                                     pred_taken, bp_history, tid);
 194
 195     // Now lookup in the BTB or RAS.
 196     if (pred_taken) {
 197         if (inst->isReturn()) {
 198             ++usedRAS;
 199             predict_record.wasReturn = true;
 200             // If it's a function return call, then look up the address
 201             // in the RAS.
 202             TheISA::PCState rasTop = RAS[tid].top();
 203             target = TheISA::buildRetPC(pc, rasTop);
 204
 205             // Record the top entry of the RAS, and its index.
 206             predict_record.usedRAS = true;
 207             predict_record.RASIndex = RAS[tid].topIdx();
 208             predict_record.RASTarget = rasTop;
 209
 210             RAS[tid].pop();
 211
 212             DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %s is a return, "
 213                     "RAS predicted target: %s, RAS index: %i.\n",
 214                     tid, inst->pcState(), target, predict_record.RASIndex);
 215         } else {
 216             ++BTBLookups;
 217
 218             if (inst->isCall()) {
 219                 RAS[tid].push(pc);
 220                 predict_record.pushedRAS = true;
 221                 // Record that it was a call so that the top RAS entry can
 222                 // be popped off if the speculation is incorrect.
 223                 predict_record.wasCall = true;
 224
 225                 DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %s was a "
 226                         "call, adding %s to the RAS index: %i.\n",
 227                         tid, inst->pcState(), pc, RAS[tid].topIdx());
 228             }
 229
 230             if (BTB.valid(pc.instAddr(), tid)) {
 231                 ++BTBHits;
 232                 predict_record.validBTB = true;
 233
 234                 // If it's not a return, use the BTB to get the target addr.
 235                 target = BTB.lookup(pc.instAddr(), tid);
 236
 237                 DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %s predicted"
 238                         " target is %s.\n", tid, inst->pcState(), target);
 239
 240             } else {
 241                 DPRINTF(Fetch, "BranchPred: [tid:%i]: BTB doesn't have a "
 242                         "valid entry.\n",tid);
 243                 pred_taken = false;
 244                 // The Direction of the branch predictor is altered because the
 245                 // BTB did not have an entry
 246                 // The predictor needs to be updated accordingly
 247                 if (!inst->isCall() && !inst->isReturn()) {
 248                       BPBTBUpdate(pc.instAddr(), bp_history);
 249                       DPRINTF(Fetch, "BranchPred: [tid:%i]:[sn:%i] BPBTBUpdate"
 250                               " called for %s\n",
 251                               tid, inst->seqNum, inst->pcState());
 252                 } else if (inst->isCall() && !inst->isUncondCtrl()) {
 253                       RAS[tid].pop();
 254                       predict_record.pushedRAS = false;
 255                 }
 256                 TheISA::advancePC(target, inst->staticInst);
 257             }
 258
 259         }
 260     } else {
 261         if (inst->isReturn()) {
 262            predict_record.wasReturn = true;
 263         }
 264         TheISA::advancePC(target, inst->staticInst);
 265     }
 266
 267     pc = target;
 268
 269     predHist[tid].push_front(predict_record);
 270
 271     DPRINTF(Fetch, "BranchPred: [tid:%i]: [sn:%i]: History entry added."
 272             "predHist.size(): %i\n", tid, inst->seqNum, predHist[tid].size());
 273
 274     return pred_taken;
 275 }
 276
 277 template <class Impl>
 278 void
 279 BPredUnit<Impl>::update(const InstSeqNum &done_sn, ThreadID tid)
 280 {
 281     DPRINTF(Fetch, "BranchPred: [tid:%i]: Committing branches until "
 282             "[sn:%lli].\n", tid, done_sn);
 283
 284     while (!predHist[tid].empty() &&
 285            predHist[tid].back().seqNum <= done_sn) {
 286         // Update the branch predictor with the correct results.
 287         BPUpdate(predHist[tid].back().pc,
 288                  predHist[tid].back().predTaken,
 289                  predHist[tid].back().bpHistory, false);
 290
 291         predHist[tid].pop_back();
 292     }
 293 }
 294
 295 template <class Impl>
 296 void
 297 BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn, ThreadID tid)
 298 {
 299     History &pred_hist = predHist[tid];
 300
 301     while (!pred_hist.empty() &&
 302            pred_hist.front().seqNum > squashed_sn) {
 303         if (pred_hist.front().usedRAS) {
 304             DPRINTF(Fetch, "BranchPred: [tid:%i]: Restoring top of RAS to: %i,"
 305                     " target: %s.\n", tid,
 306                     pred_hist.front().RASIndex, pred_hist.front().RASTarget);
 307
 308             RAS[tid].restore(pred_hist.front().RASIndex,
 309                              pred_hist.front().RASTarget);
 310         } else if(pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
 311                  // Was a call but predicated false. Pop RAS here
 312                  DPRINTF(Fetch, "BranchPred: [tid: %i] Squashing"
 313                          "  Call [sn:%i] PC: %s Popping RAS\n", tid,
 314                          pred_hist.front().seqNum, pred_hist.front().pc);
 315                  RAS[tid].pop();
 316            }
 317
 318         // This call should delete the bpHistory.
 319         BPSquash(pred_hist.front().bpHistory);
 320
 321         DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i] "
 322                 "PC %s.\n", tid, pred_hist.front().seqNum,
 323                 pred_hist.front().pc);
 324
 325         pred_hist.pop_front();
 326
 327         DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n",
 328                 tid, predHist[tid].size());
 329     }
 330
 331 }
 332
 333 template <class Impl>
 334 void
 335 BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn,
 336                         const TheISA::PCState &corrTarget,
 337                         bool actually_taken,
 338                         ThreadID tid)
 339 {
 340     // Now that we know that a branch was mispredicted, we need to undo
 341     // all the branches that have been seen up until this branch and
 342     // fix up everything.
 343     // NOTE: This should be call conceivably in 2 scenarios:
 344     // (1) After an branch is executed, it updates its status in the ROB
 345     //     The commit stage then checks the ROB update and sends a signal to
 346     //     the fetch stage to squash history after the mispredict
 347     // (2) In the decode stage, you can find out early if a unconditional
 348     //     PC-relative, branch was predicted incorrectly. If so, a signal
 349     //     to the fetch stage is sent to squash history after the mispredict
 350
 351     History &pred_hist = predHist[tid];
 352
 353     ++condIncorrect;
 354
 355     DPRINTF(Fetch, "BranchPred: [tid:%i]: Squashing from sequence number %i, "
 356             "setting target to %s.\n",
 357             tid, squashed_sn, corrTarget);
 358
 359     // Squash All Branches AFTER this mispredicted branch
 360     squash(squashed_sn, tid);
 361
 362     // If there's a squash due to a syscall, there may not be an entry
 363     // corresponding to the squash.  In that case, don't bother trying to
 364     // fix up the entry.
 365     if (!pred_hist.empty()) {
 366
 367         HistoryIt hist_it = pred_hist.begin();
 368         //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
 369         //                       squashed_sn);
 370
 371         //assert(hist_it != pred_hist.end());
 372         if (pred_hist.front().seqNum != squashed_sn) {
 373             DPRINTF(Fetch, "Front sn %i != Squash sn %i\n",
 374                     pred_hist.front().seqNum, squashed_sn);
 375
 376             assert(pred_hist.front().seqNum == squashed_sn);
 377         }
 378
 379
 380         if ((*hist_it).usedRAS) {
 381             ++RASIncorrect;
 382         }
 383
 384         BPUpdate((*hist_it).pc, actually_taken,
 385                  pred_hist.front().bpHistory, true);
 386         if (actually_taken) {
 387             if (hist_it->wasReturn && !hist_it->usedRAS) {
 388                  DPRINTF(Fetch, "BranchPred: [tid: %i] Incorrectly predicted"
 389                            "  return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
 390                             hist_it->pc);
 391                  RAS[tid].pop();
 392             }
 393            DPRINTF(Fetch,"BranchPred: [tid: %i] BTB Update called for [sn:%i]"
 394                             " PC: %s\n", tid,hist_it->seqNum, hist_it->pc);
 395
 396
 397             BTB.update((*hist_it).pc, corrTarget, tid);
 398
 399         } else {
 400            //Actually not Taken
 401            if (hist_it->usedRAS) {
 402                 DPRINTF(Fetch,"BranchPred: [tid: %i] Incorrectly predicted"
 403                            "  return [sn:%i] PC: %s Restoring RAS\n", tid,
 404                            hist_it->seqNum, hist_it->pc);
 405                 DPRINTF(Fetch, "BranchPred: [tid:%i]: Restoring top of RAS"
 406                                " to: %i, target: %s.\n", tid,
 407                               hist_it->RASIndex, hist_it->RASTarget);
 408                 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
 409
 410            } else if (hist_it->wasCall && hist_it->pushedRAS) {
 411                  //Was a Call but predicated false. Pop RAS here
 412                  DPRINTF(Fetch, "BranchPred: [tid: %i] Incorrectly predicted"
 413                            "  Call [sn:%i] PC: %s Popping RAS\n", tid,
 414                            hist_it->seqNum, hist_it->pc);
 415                  RAS[tid].pop();
 416            }
 417         }
 418         DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i]"
 419                        " PC %s  Actually Taken: %i\n", tid, hist_it->seqNum,
 420                        hist_it->pc, actually_taken);
 421
 422         pred_hist.erase(hist_it);
 423
 424         DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n", tid,
 425                                          predHist[tid].size());
 426     }
 427 }
 428
 429 template <class Impl>
 430 void
 431 BPredUnit<Impl>::BPUncond(void * &bp_history)
 432 {
 433     // Only the tournament predictor cares about unconditional branches.
 434     if (predictor == Tournament) {
 435         tournamentBP->uncondBr(bp_history);
 436     }
 437 }
 438
 439 template <class Impl>
 440 void
 441 BPredUnit<Impl>::BPSquash(void *bp_history)
 442 {
 443     if (predictor == Local) {
 444         localBP->squash(bp_history);
 445     } else if (predictor == Tournament) {
 446         tournamentBP->squash(bp_history);
 447     } else {
 448         panic("Predictor type is unexpected value!");
 449     }
 450 }
 451
 452 template <class Impl>
 453 bool
 454 BPredUnit<Impl>::BPLookup(Addr instPC, void * &bp_history)
 455 {
 456     if (predictor == Local) {
 457         return localBP->lookup(instPC, bp_history);
 458     } else if (predictor == Tournament) {
 459         return tournamentBP->lookup(instPC, bp_history);
 460     } else {
 461         panic("Predictor type is unexpected value!");
 462     }
 463 }
 464
 465 template <class Impl>
 466 void
 467 BPredUnit<Impl>::BPBTBUpdate(Addr instPC, void * &bp_history)
 468 {
 469     if (predictor == Local) {
 470         return localBP->BTBUpdate(instPC, bp_history);
 471     } else if (predictor == Tournament) {
 472         return tournamentBP->BTBUpdate(instPC, bp_history);
 473     } else {
 474         panic("Predictor type is unexpected value!");
 475     }
 476 }
 477
 478 template <class Impl>
 479 void
 480 BPredUnit<Impl>::BPUpdate(Addr instPC, bool taken, void *bp_history,
 481                  bool squashed)
 482 {
 483     if (predictor == Local) {
 484         localBP->update(instPC, taken, bp_history);
 485     } else if (predictor == Tournament) {
 486         tournamentBP->update(instPC, taken, bp_history, squashed);
 487     } else {
 488         panic("Predictor type is unexpected value!");
 489     }
 490 }
 491
 492 template <class Impl>
 493 void
 494 BPredUnit<Impl>::dump()
 495 {
 496     HistoryIt pred_hist_it;
 497
 498     for (int i = 0; i < Impl::MaxThreads; ++i) {
 499         if (!predHist[i].empty()) {
 500             pred_hist_it = predHist[i].begin();
 501
 502             cprintf("predHist[%i].size(): %i\n", i, predHist[i].size());
 503
 504             while (pred_hist_it != predHist[i].end()) {
 505                 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
 506                         "bpHistory:%#x\n",
 507                         pred_hist_it->seqNum, pred_hist_it->pc,
 508                         pred_hist_it->tid, pred_hist_it->predTaken,
 509                         pred_hist_it->bpHistory);
 510                 pred_hist_it++;
 511             }
 512
 513             cprintf("\n");
 514         }
 515     }
 516 }