src/cpu/inorder/resources/bpred_unit.cc

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