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