src/cpu/o3/bpred_unit_impl.hh

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