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 "arch/types.hh"
  32 #include "arch/isa_traits.hh"
  33 #include "base/trace.hh"
  34 #include "base/traceflags.hh"
  35 #include "cpu/o3/bpred_unit.hh"
  36
  37 template<class Impl>
  38 BPredUnit<Impl>::BPredUnit(Params *params)
  39   : BTB(params->BTBEntries,
  40         params->BTBTagSize,
  41         params->instShiftAmt)
  42 {
  43     // Setup the selected predictor.
  44     if (params->predType == "local") {
  45         localBP = new LocalBP(params->localPredictorSize,
  46                               params->localCtrBits,
  47                               params->instShiftAmt);
  48         predictor = Local;
  49     } else if (params->predType == "tournament") {
  50         tournamentBP = new TournamentBP(params->localPredictorSize,
  51                                         params->localCtrBits,
  52                                         params->localHistoryTableSize,
  53                                         params->localHistoryBits,
  54                                         params->globalPredictorSize,
  55                                         params->globalHistoryBits,
  56                                         params->globalCtrBits,
  57                                         params->choicePredictorSize,
  58                                         params->choiceCtrBits,
  59                                         params->instShiftAmt);
  60         predictor = Tournament;
  61     } else {
  62         fatal("Invalid BP selected!");
  63     }
  64
  65     for (int i=0; i < Impl::MaxThreads; i++)
  66         RAS[i].init(params->RASSize);
  67 }
  68
  69 template <class Impl>
  70 void
  71 BPredUnit<Impl>::regStats()
  72 {
  73     lookups
  74         .name(name() + ".BPredUnit.lookups")
  75         .desc("Number of BP lookups")
  76         ;
  77
  78     condPredicted
  79         .name(name() + ".BPredUnit.condPredicted")
  80         .desc("Number of conditional branches predicted")
  81         ;
  82
  83     condIncorrect
  84         .name(name() + ".BPredUnit.condIncorrect")
  85         .desc("Number of conditional branches incorrect")
  86         ;
  87
  88     BTBLookups
  89         .name(name() + ".BPredUnit.BTBLookups")
  90         .desc("Number of BTB lookups")
  91         ;
  92
  93     BTBHits
  94         .name(name() + ".BPredUnit.BTBHits")
  95         .desc("Number of BTB hits")
  96         ;
  97
  98     BTBCorrect
  99         .name(name() + ".BPredUnit.BTBCorrect")
 100         .desc("Number of correct BTB predictions (this stat may not "
 101               "work properly.")
 102         ;
 103
 104     usedRAS
 105         .name(name() + ".BPredUnit.usedRAS")
 106         .desc("Number of times the RAS was used to get a target.")
 107         ;
 108
 109     RASIncorrect
 110         .name(name() + ".BPredUnit.RASInCorrect")
 111         .desc("Number of incorrect RAS predictions.")
 112         ;
 113 }
 114
 115 template <class Impl>
 116 void
 117 BPredUnit<Impl>::switchOut()
 118 {
 119     // Clear any state upon switch out.
 120     for (int i = 0; i < Impl::MaxThreads; ++i) {
 121         squash(0, i);
 122     }
 123 }
 124
 125 template <class Impl>
 126 void
 127 BPredUnit<Impl>::takeOverFrom()
 128 {
 129     // Can reset all predictor state, but it's not necessarily better
 130     // than leaving it be.
 131 /*
 132     for (int i = 0; i < Impl::MaxThreads; ++i)
 133         RAS[i].reset();
 134
 135     BP.reset();
 136     BTB.reset();
 137 */
 138 }
 139
 140 template <class Impl>
 141 bool
 142 BPredUnit<Impl>::predict(DynInstPtr &inst, Addr &PC, unsigned tid)
 143 {
 144     // See if branch predictor predicts taken.
 145     // If so, get its target addr either from the BTB or the RAS.
 146     // Save off record of branch stuff so the RAS can be fixed
 147     // up once it's done.
 148
 149     using TheISA::MachInst;
 150
 151     bool pred_taken = false;
 152     Addr target = PC;
 153
 154     ++lookups;
 155
 156     void *bp_history = NULL;
 157
 158     if (inst->isUncondCtrl()) {
 159         DPRINTF(Fetch, "BranchPred: [tid:%i]: Unconditional control.\n", tid);
 160         pred_taken = true;
 161         // Tell the BP there was an unconditional branch.
 162         BPUncond(bp_history);
 163     } else {
 164         ++condPredicted;
 165
 166         pred_taken = BPLookup(PC, bp_history);
 167
 168         DPRINTF(Fetch, "BranchPred: [tid:%i]: Branch predictor predicted %i "
 169                 "for PC %#x\n",
 170                 tid, pred_taken, inst->readPC());
 171     }
 172
 173     PredictorHistory predict_record(inst->seqNum, PC, pred_taken,
 174                                     bp_history, tid);
 175
 176     // Now lookup in the BTB or RAS.
 177     if (pred_taken) {
 178         if (inst->isReturn()) {
 179             ++usedRAS;
 180
 181             // If it's a function return call, then look up the address
 182             // in the RAS.
 183             target = RAS[tid].top();
 184
 185             // Record the top entry of the RAS, and its index.
 186             predict_record.usedRAS = true;
 187             predict_record.RASIndex = RAS[tid].topIdx();
 188             predict_record.RASTarget = target;
 189
 190             assert(predict_record.RASIndex < 16);
 191
 192             RAS[tid].pop();
 193
 194             DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %#x is a return, "
 195                     "RAS predicted target: %#x, RAS index: %i.\n",
 196                     tid, inst->readPC(), target, predict_record.RASIndex);
 197         } else {
 198             ++BTBLookups;
 199
 200             if (inst->isCall()) {
 201 #if ISA_HAS_DELAY_SLOT
 202                 Addr ras_pc = PC + (2 * sizeof(MachInst)); // Next Next PC
 203 #else
 204                 Addr ras_pc = PC + sizeof(MachInst); // Next PC
 205 #endif
 206                 RAS[tid].push(ras_pc);
 207
 208                 // Record that it was a call so that the top RAS entry can
 209                 // be popped off if the speculation is incorrect.
 210                 predict_record.wasCall = true;
 211
 212                 DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %#x was a call"
 213                         ", adding %#x to the RAS index: %i.\n",
 214                         tid, inst->readPC(), ras_pc, RAS[tid].topIdx());
 215             }
 216
 217             if (BTB.valid(PC, tid)) {
 218                 ++BTBHits;
 219
 220                 // If it's not a return, use the BTB to get the target addr.
 221                 target = BTB.lookup(PC, tid);
 222
 223                 DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %#x predicted"
 224                         " target is %#x.\n",
 225                         tid, inst->readPC(), target);
 226
 227             } else {
 228                 DPRINTF(Fetch, "BranchPred: [tid:%i]: BTB doesn't have a "
 229                         "valid entry.\n",tid);
 230                 pred_taken = false;
 231             }
 232
 233         }
 234     }
 235
 236     PC = target;
 237
 238     predHist[tid].push_front(predict_record);
 239
 240     DPRINTF(Fetch, "[tid:%i]: predHist.size(): %i\n", tid, predHist[tid].size());
 241
 242     return pred_taken;
 243 }
 244
 245 template <class Impl>
 246 void
 247 BPredUnit<Impl>::update(const InstSeqNum &done_sn, unsigned tid)
 248 {
 249     DPRINTF(Fetch, "BranchPred: [tid:%i]: Commiting branches until "
 250             "[sn:%lli].\n", tid, done_sn);
 251
 252     while (!predHist[tid].empty() &&
 253            predHist[tid].back().seqNum <= done_sn) {
 254         // Update the branch predictor with the correct results.
 255         BPUpdate(predHist[tid].back().PC,
 256                  predHist[tid].back().predTaken,
 257                  predHist[tid].back().bpHistory);
 258
 259         predHist[tid].pop_back();
 260     }
 261 }
 262
 263 template <class Impl>
 264 void
 265 BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn, unsigned tid)
 266 {
 267     History &pred_hist = predHist[tid];
 268
 269     while (!pred_hist.empty() &&
 270            pred_hist.front().seqNum > squashed_sn) {
 271         if (pred_hist.front().usedRAS) {
 272             DPRINTF(Fetch, "BranchPred: [tid:%i]: Restoring top of RAS to: %i,"
 273                     " target: %#x.\n",
 274                     tid,
 275                     pred_hist.front().RASIndex,
 276                     pred_hist.front().RASTarget);
 277
 278             RAS[tid].restore(pred_hist.front().RASIndex,
 279                              pred_hist.front().RASTarget);
 280         } else if (pred_hist.front().wasCall) {
 281             DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing speculative entry "
 282                     "added to the RAS.\n",tid);
 283
 284             RAS[tid].pop();
 285         }
 286
 287         // This call should delete the bpHistory.
 288         BPSquash(pred_hist.front().bpHistory);
 289
 290         pred_hist.pop_front();
 291     }
 292
 293 }
 294
 295 template <class Impl>
 296 void
 297 BPredUnit<Impl>::squash(const InstSeqNum &squashed_sn,
 298                         const Addr &corr_target,
 299                         const bool actually_taken,
 300                         unsigned tid)
 301 {
 302     // Now that we know that a branch was mispredicted, we need to undo
 303     // all the branches that have been seen up until this branch and
 304     // fix up everything.
 305
 306     History &pred_hist = predHist[tid];
 307
 308     ++condIncorrect;
 309
 310     DPRINTF(Fetch, "BranchPred: [tid:%i]: Squashing from sequence number %i, "
 311             "setting target to %#x.\n",
 312             tid, squashed_sn, corr_target);
 313
 314     squash(squashed_sn, tid);
 315
 316     // If there's a squash due to a syscall, there may not be an entry
 317     // corresponding to the squash.  In that case, don't bother trying to
 318     // fix up the entry.
 319     if (!pred_hist.empty()) {
 320         assert(pred_hist.front().seqNum == squashed_sn);
 321         if (pred_hist.front().usedRAS) {
 322             ++RASIncorrect;
 323         }
 324
 325         BPUpdate(pred_hist.front().PC, actually_taken,
 326                  pred_hist.front().bpHistory);
 327
 328         BTB.update(pred_hist.front().PC, corr_target, tid);
 329         pred_hist.pop_front();
 330     }
 331 }
 332
 333 template <class Impl>
 334 void
 335 BPredUnit<Impl>::BPUncond(void * &bp_history)
 336 {
 337     // Only the tournament predictor cares about unconditional branches.
 338     if (predictor == Tournament) {
 339         tournamentBP->uncondBr(bp_history);
 340     }
 341 }
 342
 343 template <class Impl>
 344 void
 345 BPredUnit<Impl>::BPSquash(void *bp_history)
 346 {
 347     if (predictor == Local) {
 348         localBP->squash(bp_history);
 349     } else if (predictor == Tournament) {
 350         tournamentBP->squash(bp_history);
 351     } else {
 352         panic("Predictor type is unexpected value!");
 353     }
 354 }
 355
 356 template <class Impl>
 357 bool
 358 BPredUnit<Impl>::BPLookup(Addr &inst_PC, void * &bp_history)
 359 {
 360     if (predictor == Local) {
 361         return localBP->lookup(inst_PC, bp_history);
 362     } else if (predictor == Tournament) {
 363         return tournamentBP->lookup(inst_PC, bp_history);
 364     } else {
 365         panic("Predictor type is unexpected value!");
 366     }
 367 }
 368
 369 template <class Impl>
 370 void
 371 BPredUnit<Impl>::BPUpdate(Addr &inst_PC, bool taken, void *bp_history)
 372 {
 373     if (predictor == Local) {
 374         localBP->update(inst_PC, taken, bp_history);
 375     } else if (predictor == Tournament) {
 376         tournamentBP->update(inst_PC, taken, bp_history);
 377     } else {
 378         panic("Predictor type is unexpected value!");
 379     }
 380 }
 381
 382 template <class Impl>
 383 void
 384 BPredUnit<Impl>::dump()
 385 {
 386     typename History::iterator pred_hist_it;
 387
 388     for (int i = 0; i < Impl::MaxThreads; ++i) {
 389         if (!predHist[i].empty()) {
 390             pred_hist_it = predHist[i].begin();
 391
 392             cprintf("predHist[%i].size(): %i\n", i, predHist[i].size());
 393
 394             while (pred_hist_it != predHist[i].end()) {
 395                 cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
 396                         "bpHistory:%#x\n",
 397                         (*pred_hist_it).seqNum, (*pred_hist_it).PC,
 398                         (*pred_hist_it).tid, (*pred_hist_it).predTaken,
 399                         (*pred_hist_it).bpHistory);
 400                 pred_hist_it++;
 401             }
 402
 403             cprintf("\n");
 404         }
 405     }
 406 }