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             assert(predict_record.RASIndex < 16);
 211
 212             RAS[tid].pop();
 213
 214             DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %s is a return, "
 215                     "RAS predicted target: %s, RAS index: %i.\n",
 216                     tid, inst->pcState(), target, predict_record.RASIndex);
 217         } else {
 218             ++BTBLookups;
 219
 220             if (inst->isCall()) {
 221                 RAS[tid].push(pc);
 222                 predict_record.pushedRAS = true;
 223                 // Record that it was a call so that the top RAS entry can
 224                 // be popped off if the speculation is incorrect.
 225                 predict_record.wasCall = true;
 226
 227                 DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %s was a "
 228                         "call, adding %s to the RAS index: %i.\n",
 229                         tid, inst->pcState(), pc, RAS[tid].topIdx());
 230             }
 231
 232             if (BTB.valid(pc.instAddr(), tid)) {
 233                 ++BTBHits;
 234                 predict_record.validBTB = true;
 235
 236                 // If it's not a return, use the BTB to get the target addr.
 237                 target = BTB.lookup(pc.instAddr(), tid);
 238
 239                 DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %s predicted"
 240                         " target is %s.\n", tid, inst->pcState(), target);
 241
 242             } else {
 243                 DPRINTF(Fetch, "BranchPred: [tid:%i]: BTB doesn't have a "
 244                         "valid entry.\n",tid);
 245                 pred_taken = false;
 246                 // The Direction of the branch predictor is altered because the
 247                 // BTB did not have an entry
 248                 // The predictor needs to be updated accordingly
 249                 if (!inst->isCall() && !inst->isReturn()) {
 250                       BPBTBUpdate(pc.instAddr(), bp_history);
 251                       DPRINTF(Fetch, "BranchPred: [tid:%i]:[sn:%i] BPBTBUpdate"
 252                               " called for %s\n",
 253                               tid, inst->seqNum, inst->pcState());
 254                 } else if (inst->isCall() && !inst->isUncondCtrl()) {
 255                       RAS[tid].pop();
 256                       predict_record.pushedRAS = false;
 257                 }
 258                 TheISA::advancePC(target, inst->staticInst);
 259             }
 260
 261         }
 262     } else {
 263         if (inst->isReturn()) {
 264            predict_record.wasReturn = true;
 265         }
 266         TheISA::advancePC(target, inst->staticInst);
 267     }
 268
 269     pc = target;
 270
 271     predHist[tid].push_front(predict_record);
 272
 273     DPRINTF(Fetch, "BranchPred: [tid:%i]: [sn:%i]: History entry added."
 274             "predHist.size(): %i\n", tid, inst->seqNum, predHist[tid].size());
 275
 276     return pred_taken;
 277 }
 278
 279 template <class Impl>
 280 void
 281 BPredUnit<Impl>::update(const InstSeqNum &done_sn, ThreadID tid)
 282 {
 283     DPRINTF(Fetch, "BranchPred: [tid:%i]: Committing branches until "
 284             "[sn:%lli].\n", tid, done_sn);
 285
 286     while (!predHist[tid].empty() &&
 287            predHist[tid].back().seqNum <= done_sn) {
 288         // Update the branch predictor with the correct results.
 289         BPUpdate(predHist[tid].back().pc,
 290                  predHist[tid].back().predTaken,
 291                  predHist[tid].back().bpHistory, false);
 292
 293         predHist[tid].pop_back();
 294     }
 295 }
 296
 297 template <class Impl>
 298 void
 299 BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn, ThreadID tid)
 300 {
 301     History &pred_hist = predHist[tid];
 302
 303     while (!pred_hist.empty() &&
 304            pred_hist.front().seqNum > squashed_sn) {
 305         if (pred_hist.front().usedRAS) {
 306             DPRINTF(Fetch, "BranchPred: [tid:%i]: Restoring top of RAS to: %i,"
 307                     " target: %s.\n", tid,
 308                     pred_hist.front().RASIndex, pred_hist.front().RASTarget);
 309
 310             RAS[tid].restore(pred_hist.front().RASIndex,
 311                              pred_hist.front().RASTarget);
 312         } else if(pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
 313                  // Was a call but predicated false. Pop RAS here
 314                  DPRINTF(Fetch, "BranchPred: [tid: %i] Squashing"
 315                          "  Call [sn:%i] PC: %s Popping RAS\n", tid,
 316                          pred_hist.front().seqNum, pred_hist.front().pc);
 317                  RAS[tid].pop();
 318            }
 319
 320         // This call should delete the bpHistory.
 321         BPSquash(pred_hist.front().bpHistory);
 322
 323         DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i] "
 324                 "PC %s.\n", tid, pred_hist.front().seqNum,
 325                 pred_hist.front().pc);
 326
 327         pred_hist.pop_front();
 328
 329         DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n",
 330                 tid, predHist[tid].size());
 331     }
 332
 333 }
 334
 335 template <class Impl>
 336 void
 337 BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn,
 338                         const TheISA::PCState &corrTarget,
 339                         bool actually_taken,
 340                         ThreadID tid)
 341 {
 342     // Now that we know that a branch was mispredicted, we need to undo
 343     // all the branches that have been seen up until this branch and
 344     // fix up everything.
 345     // NOTE: This should be call conceivably in 2 scenarios:
 346     // (1) After an branch is executed, it updates its status in the ROB
 347     //     The commit stage then checks the ROB update and sends a signal to
 348     //     the fetch stage to squash history after the mispredict
 349     // (2) In the decode stage, you can find out early if a unconditional
 350     //     PC-relative, branch was predicted incorrectly. If so, a signal
 351     //     to the fetch stage is sent to squash history after the mispredict
 352
 353     History &pred_hist = predHist[tid];
 354
 355     ++condIncorrect;
 356
 357     DPRINTF(Fetch, "BranchPred: [tid:%i]: Squashing from sequence number %i, "
 358             "setting target to %s.\n",
 359             tid, squashed_sn, corrTarget);
 360
 361     // Squash All Branches AFTER this mispredicted branch
 362     squash(squashed_sn, tid);
 363
 364     // If there's a squash due to a syscall, there may not be an entry
 365     // corresponding to the squash.  In that case, don't bother trying to
 366     // fix up the entry.
 367     if (!pred_hist.empty()) {
 368
 369         HistoryIt hist_it = pred_hist.begin();
 370         //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
 371         //                       squashed_sn);
 372
 373         //assert(hist_it != pred_hist.end());
 374         if (pred_hist.front().seqNum != squashed_sn) {
 375             DPRINTF(Fetch, "Front sn %i != Squash sn %i\n",
 376                     pred_hist.front().seqNum, squashed_sn);
 377
 378             assert(pred_hist.front().seqNum == squashed_sn);
 379         }
 380
 381
 382         if ((*hist_it).usedRAS) {
 383             ++RASIncorrect;
 384         }
 385
 386         BPUpdate((*hist_it).pc, actually_taken,
 387                  pred_hist.front().bpHistory, true);
 388         if (actually_taken) {
 389             if (hist_it->wasReturn && !hist_it->usedRAS) {
 390                  DPRINTF(Fetch, "BranchPred: [tid: %i] Incorrectly predicted"
 391                            "  return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
 392                             hist_it->pc);
 393                  RAS[tid].pop();
 394             }
 395            DPRINTF(Fetch,"BranchPred: [tid: %i] BTB Update called for [sn:%i]"
 396                             " PC: %s\n", tid,hist_it->seqNum, hist_it->pc);
 397
 398
 399             BTB.update((*hist_it).pc, corrTarget, tid);
 400
 401         } else {
 402            //Actually not Taken
 403            if (hist_it->usedRAS) {
 404                 DPRINTF(Fetch,"BranchPred: [tid: %i] Incorrectly predicted"
 405                            "  return [sn:%i] PC: %s Restoring RAS\n", tid,
 406                            hist_it->seqNum, hist_it->pc);
 407                 DPRINTF(Fetch, "BranchPred: [tid:%i]: Restoring top of RAS"
 408                                " to: %i, target: %s.\n", tid,
 409                               hist_it->RASIndex, hist_it->RASTarget);
 410                 RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
 411
 412            } else if (hist_it->wasCall && hist_it->pushedRAS) {
 413                  //Was a Call but predicated false. Pop RAS here
 414                  DPRINTF(Fetch, "BranchPred: [tid: %i] Incorrectly predicted"
 415                            "  Call [sn:%i] PC: %s Popping RAS\n", tid,
 416                            hist_it->seqNum, hist_it->pc);
 417                  RAS[tid].pop();
 418            }
 419         }
 420         DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing history for [sn:%i]"
 421                        " PC %s  Actually Taken: %i\n", tid, hist_it->seqNum,
 422                        hist_it->pc, actually_taken);
 423
 424         pred_hist.erase(hist_it);
 425
 426         DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n", tid,
 427                                          predHist[tid].size());
 428     }
 429 }
 430
 431 template <class Impl>
 432 void
 433 BPredUnit<Impl>::BPUncond(void * &bp_history)
 434 {
 435     // Only the tournament predictor cares about unconditional branches.
 436     if (predictor == Tournament) {
 437         tournamentBP->uncondBr(bp_history);
 438     }
 439 }
 440
 441 template <class Impl>
 442 void
 443 BPredUnit<Impl>::BPSquash(void *bp_history)
 444 {
 445     if (predictor == Local) {
 446         localBP->squash(bp_history);
 447     } else if (predictor == Tournament) {
 448         tournamentBP->squash(bp_history);
 449     } else {
 450         panic("Predictor type is unexpected value!");
 451     }
 452 }
 453
 454 template <class Impl>
 455 bool
 456 BPredUnit<Impl>::BPLookup(Addr instPC, void * &bp_history)
 457 {
 458     if (predictor == Local) {
 459         return localBP->lookup(instPC, bp_history);
 460     } else if (predictor == Tournament) {
 461         return tournamentBP->lookup(instPC, bp_history);
 462     } else {
 463         panic("Predictor type is unexpected value!");
 464     }
 465 }
 466
 467 template <class Impl>
 468 void
 469 BPredUnit<Impl>::BPBTBUpdate(Addr instPC, void * &bp_history)
 470 {
 471     if (predictor == Local) {
 472         return localBP->BTBUpdate(instPC, bp_history);
 473     } else if (predictor == Tournament) {
 474         return tournamentBP->BTBUpdate(instPC, bp_history);
 475     } else {
 476         panic("Predictor type is unexpected value!");
 477     }
 478 }
 479
 480 template <class Impl>
 481 void
 482 BPredUnit<Impl>::BPUpdate(Addr instPC, bool taken, void *bp_history,
 483                  bool squashed)
 484 {
 485     if (predictor == Local) {
 486         localBP->update(instPC, taken, bp_history);
 487     } else if (predictor == Tournament) {
 488         tournamentBP->update(instPC, taken, bp_history, squashed);
 489     } else {
 490         panic("Predictor type is unexpected value!");
 491     }
 492 }
 493
 494 template <class Impl>
 495 void
 496 BPredUnit<Impl>::dump()
 497 {
 498     HistoryIt pred_hist_it;
 499
 500     for (int i = 0; i < Impl::MaxThreads; ++i) {
 501         if (!predHist[i].empty()) {
 502             pred_hist_it = predHist[i].begin();
 503
 504             cprintf("predHist[%i].size(): %i\n", i, predHist[i].size());
 505
 506             while (pred_hist_it != predHist[i].end()) {
 507                 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
 508                         "bpHistory:%#x\n",
 509                         pred_hist_it->seqNum, pred_hist_it->pc,
 510                         pred_hist_it->tid, pred_hist_it->predTaken,
 511                         pred_hist_it->bpHistory);
 512                 pred_hist_it++;
 513             }
 514
 515             cprintf("\n");
 516         }
 517     }
 518 }