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