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 TwobitBPredUnit<Impl>::TwobitBPredUnit(Params *params)
  42   : BP(params->localPredictorSize,
  43        params->localCtrBits,
  44        params->instShiftAmt),
  45     BTB(params->BTBEntries,
  46         params->BTBTagSize,
  47         params->instShiftAmt)
  48 {
  49     for (int i=0; i < Impl::MaxThreads; i++)
  50         RAS[i].init(params->RASSize);
  51 }
  52
  53 template <class Impl>
  54 void
  55 TwobitBPredUnit<Impl>::regStats()
  56 {
  57     lookups
  58         .name(name() + ".BPredUnit.lookups")
  59         .desc("Number of BP lookups")
  60         ;
  61
  62     condPredicted
  63         .name(name() + ".BPredUnit.condPredicted")
  64         .desc("Number of conditional branches predicted")
  65         ;
  66
  67     condIncorrect
  68         .name(name() + ".BPredUnit.condIncorrect")
  69         .desc("Number of conditional branches incorrect")
  70         ;
  71
  72     BTBLookups
  73         .name(name() + ".BPredUnit.BTBLookups")
  74         .desc("Number of BTB lookups")
  75         ;
  76
  77     BTBHits
  78         .name(name() + ".BPredUnit.BTBHits")
  79         .desc("Number of BTB hits")
  80         ;
  81
  82     BTBCorrect
  83         .name(name() + ".BPredUnit.BTBCorrect")
  84         .desc("Number of correct BTB predictions (this stat may not "
  85               "work properly.")
  86         ;
  87
  88     usedRAS
  89         .name(name() + ".BPredUnit.usedRAS")
  90         .desc("Number of times the RAS was used to get a target.")
  91         ;
  92
  93     RASIncorrect
  94         .name(name() + ".BPredUnit.RASInCorrect")
  95         .desc("Number of incorrect RAS predictions.")
  96         ;
  97 }
  98
  99 template <class Impl>
 100 void
 101 TwobitBPredUnit<Impl>::switchOut()
 102 {
 103     for (int i = 0; i < Impl::MaxThreads; ++i) {
 104         predHist[i].clear();
 105     }
 106 }
 107
 108 template <class Impl>
 109 void
 110 TwobitBPredUnit<Impl>::takeOverFrom()
 111 {
 112 /*
 113     for (int i = 0; i < Impl::MaxThreads; ++i)
 114         RAS[i].reset();
 115
 116     BP.reset();
 117     BTB.reset();
 118 */
 119 }
 120
 121 template <class Impl>
 122 bool
 123 TwobitBPredUnit<Impl>::predict(DynInstPtr &inst, Addr &PC, unsigned tid)
 124 {
 125     // See if branch predictor predicts taken.
 126     // If so, get its target addr either from the BTB or the RAS.
 127     // Once that's done, speculatively update the predictor?
 128     // Save off record of branch stuff so the RAS can be fixed
 129     // up once it's done.
 130
 131     using TheISA::MachInst;
 132
 133     bool pred_taken = false;
 134     Addr target;
 135
 136     ++lookups;
 137
 138     if (inst->isUncondCtrl()) {
 139         DPRINTF(Fetch, "BranchPred: [tid:%i] Unconditional control.\n", tid);
 140         pred_taken = true;
 141     } else {
 142         ++condPredicted;
 143
 144         pred_taken = BPLookup(PC);
 145
 146         DPRINTF(Fetch, "BranchPred: [tid:%i]: Branch predictor predicted %i "
 147                 "for PC %#x\n",
 148                 tid, pred_taken, inst->readPC());
 149     }
 150
 151     PredictorHistory predict_record(inst->seqNum, PC, pred_taken, tid);
 152
 153     // Now lookup in the BTB or RAS.
 154     if (pred_taken) {
 155         if (inst->isReturn()) {
 156             ++usedRAS;
 157
 158             // If it's a function return call, then look up the address
 159             // in the RAS.
 160             target = RAS[tid].top();
 161
 162             // Record the top entry of the RAS, and its index.
 163             predict_record.usedRAS = true;
 164             predict_record.RASIndex = RAS[tid].topIdx();
 165             predict_record.RASTarget = target;
 166
 167             assert(predict_record.RASIndex < 16);
 168
 169             RAS[tid].pop();
 170
 171             DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %#x is a return, "
 172                     "RAS predicted target: %#x, RAS index: %i.\n",
 173                     tid, inst->readPC(), target, predict_record.RASIndex);
 174         } else {
 175             ++BTBLookups;
 176
 177             if (inst->isCall()) {
 178                 RAS[tid].push(PC + sizeof(MachInst));
 179
 180                 // Record that it was a call so that the top RAS entry can
 181                 // be popped off if the speculation is incorrect.
 182                 predict_record.wasCall = true;
 183
 184                 DPRINTF(Fetch, "BranchPred: [tid:%i] Instruction %#x was a call"
 185                         ", adding %#x to the RAS.\n",
 186                         tid, inst->readPC(), PC + sizeof(MachInst));
 187             }
 188
 189             if (BTB.valid(PC, tid)) {
 190                 ++BTBHits;
 191
 192                 //If it's anything else, use the BTB to get the target addr.
 193                 target = BTB.lookup(PC, tid);
 194
 195                 DPRINTF(Fetch, "BranchPred: [tid:%i]: Instruction %#x predicted"
 196                         " target is %#x.\n",
 197                         tid, inst->readPC(), target);
 198
 199             } else {
 200                 DPRINTF(Fetch, "BranchPred: [tid:%i]: BTB doesn't have a "
 201                         "valid entry.\n",tid);
 202                 pred_taken = false;
 203             }
 204
 205         }
 206     }
 207
 208     if (pred_taken) {
 209         // Set the PC and the instruction's predicted target.
 210         PC = target;
 211         inst->setPredTarg(target);
 212     } else {
 213         PC = PC + sizeof(MachInst);
 214         inst->setPredTarg(PC);
 215     }
 216
 217     predHist[tid].push_front(predict_record);
 218
 219     DPRINTF(Fetch, "[tid:%i] predHist.size(): %i\n", tid, predHist[tid].size());
 220
 221     return pred_taken;
 222 }
 223
 224 template <class Impl>
 225 void
 226 TwobitBPredUnit<Impl>::update(const InstSeqNum &done_sn, unsigned tid)
 227 {
 228     DPRINTF(Fetch, "BranchPred: [tid:%i]: Commiting branches until sequence"
 229             "number %lli.\n", tid, done_sn);
 230
 231     while (!predHist[tid].empty() &&
 232            predHist[tid].back().seqNum <= done_sn) {
 233         // Update the branch predictor with the correct results.
 234         BP.update(predHist[tid].back().PC,
 235                   predHist[tid].back().predTaken);
 236
 237         predHist[tid].pop_back();
 238     }
 239 }
 240
 241 template <class Impl>
 242 void
 243 TwobitBPredUnit<Impl>::squash(const InstSeqNum &squashed_sn, unsigned tid)
 244 {
 245     History &pred_hist = predHist[tid];
 246
 247     while (!pred_hist.empty() &&
 248            pred_hist.front().seqNum > squashed_sn) {
 249        if (pred_hist.front().usedRAS) {
 250             DPRINTF(Fetch, "BranchPred: [tid:%i]: Restoring top of RAS to: %i,"
 251                     " target: %#x.\n",
 252                     tid,
 253                     pred_hist.front().RASIndex,
 254                     pred_hist.front().RASTarget);
 255
 256             RAS[tid].restore(pred_hist.front().RASIndex,
 257                              pred_hist.front().RASTarget);
 258
 259         } else if (pred_hist.front().wasCall) {
 260             DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing speculative entry added "
 261                     "to the RAS.\n",tid);
 262
 263             RAS[tid].pop();
 264         }
 265
 266         pred_hist.pop_front();
 267     }
 268
 269 }
 270
 271 template <class Impl>
 272 void
 273 TwobitBPredUnit<Impl>::squash(const InstSeqNum &squashed_sn,
 274                               const Addr &corr_target,
 275                               const bool actually_taken,
 276                               unsigned tid)
 277 {
 278     // Now that we know that a branch was mispredicted, we need to undo
 279     // all the branches that have been seen up until this branch and
 280     // fix up everything.
 281
 282     History &pred_hist = predHist[tid];
 283
 284     ++condIncorrect;
 285
 286     DPRINTF(Fetch, "BranchPred: [tid:%i]: Squashing from sequence number %i, "
 287             "setting target to %#x.\n",
 288             tid, squashed_sn, corr_target);
 289
 290     while (!pred_hist.empty() &&
 291            pred_hist.front().seqNum > squashed_sn) {
 292         if (pred_hist.front().usedRAS) {
 293             DPRINTF(Fetch, "BranchPred: [tid:%i]: Restoring top of RAS to: %i, "
 294                     "target: %#x.\n",
 295                     tid,
 296                     pred_hist.front().RASIndex,
 297                     pred_hist.front().RASTarget);
 298
 299             RAS[tid].restore(pred_hist.front().RASIndex,
 300                              pred_hist.front().RASTarget);
 301         } else if (pred_hist.front().wasCall) {
 302             DPRINTF(Fetch, "BranchPred: [tid:%i]: Removing speculative entry"
 303                     " added to the RAS.\n", tid);
 304
 305             RAS[tid].pop();
 306         }
 307
 308         pred_hist.pop_front();
 309     }
 310
 311     // If there's a squash due to a syscall, there may not be an entry
 312     // corresponding to the squash.  In that case, don't bother trying to
 313     // fix up the entry.
 314     if (!pred_hist.empty()) {
 315         pred_hist.front().predTaken = actually_taken;
 316
 317         if (pred_hist.front().usedRAS) {
 318             ++RASIncorrect;
 319         }
 320
 321         BP.update(pred_hist.front().PC, actually_taken);
 322
 323         BTB.update(pred_hist.front().PC, corr_target, tid);
 324         pred_hist.pop_front();
 325     }
 326 }