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