bpred_unit.cc revision 11433
1/*
2 * Copyright (c) 2011-2012, 2014 ARM Limited
3 * Copyright (c) 2010 The University of Edinburgh
4 * Copyright (c) 2012 Mark D. Hill and David A. Wood
5 * All rights reserved
6 *
7 * The license below extends only to copyright in the software and shall
8 * not be construed as granting a license to any other intellectual
9 * property including but not limited to intellectual property relating
10 * to a hardware implementation of the functionality of the software
11 * licensed hereunder.  You may use the software subject to the license
12 * terms below provided that you ensure that this notice is replicated
13 * unmodified and in its entirety in all distributions of the software,
14 * modified or unmodified, in source code or in binary form.
15 *
16 * Copyright (c) 2004-2005 The Regents of The University of Michigan
17 * All rights reserved.
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions are
21 * met: redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer;
23 * redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution;
26 * neither the name of the copyright holders nor the names of its
27 * contributors may be used to endorse or promote products derived from
28 * this software without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
31 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
32 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
33 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
34 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
36 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
37 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
38 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
39 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
40 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41 *
42 * Authors: Kevin Lim
43 */
44
45#include "cpu/pred/bpred_unit.hh"
46
47#include <algorithm>
48
49#include "arch/isa_traits.hh"
50#include "arch/types.hh"
51#include "arch/utility.hh"
52#include "base/trace.hh"
53#include "config/the_isa.hh"
54#include "debug/Branch.hh"
55
56BPredUnit::BPredUnit(const Params *params)
57    : SimObject(params),
58      numThreads(params->numThreads),
59      predHist(numThreads),
60      BTB(params->BTBEntries,
61          params->BTBTagSize,
62          params->instShiftAmt,
63          params->numThreads),
64      RAS(numThreads),
65      useIndirect(params->useIndirect),
66      iPred(params->indirectHashGHR,
67            params->indirectHashTargets,
68            params->indirectSets,
69            params->indirectWays,
70            params->indirectTagSize,
71            params->indirectPathLength,
72            params->instShiftAmt,
73            params->numThreads),
74      instShiftAmt(params->instShiftAmt)
75{
76    for (auto& r : RAS)
77        r.init(params->RASSize);
78}
79
80void
81BPredUnit::regStats()
82{
83    lookups
84        .name(name() + ".lookups")
85        .desc("Number of BP lookups")
86        ;
87
88    condPredicted
89        .name(name() + ".condPredicted")
90        .desc("Number of conditional branches predicted")
91        ;
92
93    condIncorrect
94        .name(name() + ".condIncorrect")
95        .desc("Number of conditional branches incorrect")
96        ;
97
98    BTBLookups
99        .name(name() + ".BTBLookups")
100        .desc("Number of BTB lookups")
101        ;
102
103    BTBHits
104        .name(name() + ".BTBHits")
105        .desc("Number of BTB hits")
106        ;
107
108    BTBCorrect
109        .name(name() + ".BTBCorrect")
110        .desc("Number of correct BTB predictions (this stat may not "
111              "work properly.")
112        ;
113
114    BTBHitPct
115        .name(name() + ".BTBHitPct")
116        .desc("BTB Hit Percentage")
117        .precision(6);
118    BTBHitPct = (BTBHits / BTBLookups) * 100;
119
120    usedRAS
121        .name(name() + ".usedRAS")
122        .desc("Number of times the RAS was used to get a target.")
123        ;
124
125    RASIncorrect
126        .name(name() + ".RASInCorrect")
127        .desc("Number of incorrect RAS predictions.")
128        ;
129
130    indirectLookups
131        .name(name() + ".indirectLookups")
132        .desc("Number of indirect predictor lookups.")
133        ;
134
135    indirectHits
136        .name(name() + ".indirectHits")
137        .desc("Number of indirect target hits.")
138        ;
139
140    indirectMisses
141        .name(name() + ".indirectMisses")
142        .desc("Number of indirect misses.")
143        ;
144
145    indirectMispredicted
146        .name(name() + "indirectMispredicted")
147        .desc("Number of mispredicted indirect branches.")
148        ;
149
150}
151
152ProbePoints::PMUUPtr
153BPredUnit::pmuProbePoint(const char *name)
154{
155    ProbePoints::PMUUPtr ptr;
156    ptr.reset(new ProbePoints::PMU(getProbeManager(), name));
157
158    return ptr;
159}
160
161void
162BPredUnit::regProbePoints()
163{
164    ppBranches = pmuProbePoint("Branches");
165    ppMisses = pmuProbePoint("Misses");
166}
167
168void
169BPredUnit::drainSanityCheck() const
170{
171    // We shouldn't have any outstanding requests when we resume from
172    // a drained system.
173    for (const auto& ph M5_VAR_USED : predHist)
174        assert(ph.empty());
175}
176
177bool
178BPredUnit::predict(const StaticInstPtr &inst, const InstSeqNum &seqNum,
179                   TheISA::PCState &pc, ThreadID tid)
180{
181    // See if branch predictor predicts taken.
182    // If so, get its target addr either from the BTB or the RAS.
183    // Save off record of branch stuff so the RAS can be fixed
184    // up once it's done.
185
186    bool pred_taken = false;
187    TheISA::PCState target = pc;
188
189    ++lookups;
190    ppBranches->notify(1);
191
192    void *bp_history = NULL;
193
194    if (inst->isUncondCtrl()) {
195        DPRINTF(Branch, "[tid:%i]: Unconditional control.\n", tid);
196        pred_taken = true;
197        // Tell the BP there was an unconditional branch.
198        uncondBranch(pc.instAddr(), bp_history);
199    } else {
200        ++condPredicted;
201        pred_taken = lookup(pc.instAddr(), bp_history);
202
203        DPRINTF(Branch, "[tid:%i]: [sn:%i] Branch predictor"
204                " predicted %i for PC %s\n", tid, seqNum,  pred_taken, pc);
205    }
206
207    DPRINTF(Branch, "[tid:%i]: [sn:%i] Creating prediction history "
208            "for PC %s\n", tid, seqNum, pc);
209
210    PredictorHistory predict_record(seqNum, pc.instAddr(),
211                                    pred_taken, bp_history, tid);
212
213    // Now lookup in the BTB or RAS.
214    if (pred_taken) {
215        if (inst->isReturn()) {
216            ++usedRAS;
217            predict_record.wasReturn = true;
218            // If it's a function return call, then look up the address
219            // in the RAS.
220            TheISA::PCState rasTop = RAS[tid].top();
221            target = TheISA::buildRetPC(pc, rasTop);
222
223            // Record the top entry of the RAS, and its index.
224            predict_record.usedRAS = true;
225            predict_record.RASIndex = RAS[tid].topIdx();
226            predict_record.RASTarget = rasTop;
227
228            RAS[tid].pop();
229
230            DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, "
231                    "RAS predicted target: %s, RAS index: %i.\n",
232                    tid, pc, target, predict_record.RASIndex);
233        } else {
234            ++BTBLookups;
235
236            if (inst->isCall()) {
237                RAS[tid].push(pc);
238                predict_record.pushedRAS = true;
239
240                // Record that it was a call so that the top RAS entry can
241                // be popped off if the speculation is incorrect.
242                predict_record.wasCall = true;
243
244                DPRINTF(Branch, "[tid:%i]: Instruction %s was a "
245                        "call, adding %s to the RAS index: %i.\n",
246                        tid, pc, pc, RAS[tid].topIdx());
247            }
248
249            if (inst->isDirectCtrl() || !useIndirect) {
250                // Check BTB on direct branches
251                if (BTB.valid(pc.instAddr(), tid)) {
252                    ++BTBHits;
253
254                    // If it's not a return, use the BTB to get target addr.
255                    target = BTB.lookup(pc.instAddr(), tid);
256
257                    DPRINTF(Branch, "[tid:%i]: Instruction %s predicted"
258                            " target is %s.\n", tid, pc, target);
259
260                } else {
261                    DPRINTF(Branch, "[tid:%i]: BTB doesn't have a "
262                            "valid entry.\n",tid);
263                    pred_taken = false;
264                    // The Direction of the branch predictor is altered
265                    // because the BTB did not have an entry
266                    // The predictor needs to be updated accordingly
267                    if (!inst->isCall() && !inst->isReturn()) {
268                        btbUpdate(pc.instAddr(), bp_history);
269                        DPRINTF(Branch, "[tid:%i]:[sn:%i] btbUpdate"
270                                " called for %s\n", tid, seqNum, pc);
271                    } else if (inst->isCall() && !inst->isUncondCtrl()) {
272                        RAS[tid].pop();
273                        predict_record.pushedRAS = false;
274                    }
275                    TheISA::advancePC(target, inst);
276                }
277            } else {
278                predict_record.wasIndirect = true;
279                ++indirectLookups;
280                //Consult indirect predictor on indirect control
281                if (iPred.lookup(pc.instAddr(), getGHR(bp_history), target,
282                        tid)) {
283                    // Indirect predictor hit
284                    ++indirectHits;
285                    DPRINTF(Branch, "[tid:%i]: Instruction %s predicted "
286                            "indirect target is %s.\n", tid, pc, target);
287                } else {
288                    ++indirectMisses;
289                    pred_taken = false;
290                    DPRINTF(Branch, "[tid:%i]: Instruction %s no indirect "
291                            "target.\n", tid, pc);
292                    if (!inst->isCall() && !inst->isReturn()) {
293
294                    } else if (inst->isCall() && !inst->isUncondCtrl()) {
295                        RAS[tid].pop();
296                        predict_record.pushedRAS = false;
297                    }
298                    TheISA::advancePC(target, inst);
299                }
300                iPred.recordIndirect(pc.instAddr(), target.instAddr(), seqNum,
301                        tid);
302            }
303        }
304    } else {
305        if (inst->isReturn()) {
306           predict_record.wasReturn = true;
307        }
308        TheISA::advancePC(target, inst);
309    }
310
311    pc = target;
312
313    predHist[tid].push_front(predict_record);
314
315    DPRINTF(Branch, "[tid:%i]: [sn:%i]: History entry added."
316            "predHist.size(): %i\n", tid, seqNum, predHist[tid].size());
317
318    return pred_taken;
319}
320
321bool
322BPredUnit::predictInOrder(const StaticInstPtr &inst, const InstSeqNum &seqNum,
323                          int asid, TheISA::PCState &instPC,
324                          TheISA::PCState &predPC, ThreadID tid)
325{
326    // See if branch predictor predicts taken.
327    // If so, get its target addr either from the BTB or the RAS.
328    // Save off record of branch stuff so the RAS can be fixed
329    // up once it's done.
330
331    using TheISA::MachInst;
332
333    bool pred_taken = false;
334    TheISA::PCState target;
335
336    ++lookups;
337    ppBranches->notify(1);
338
339    DPRINTF(Branch, "[tid:%i] [sn:%i] %s ... PC %s doing branch "
340            "prediction\n", tid, seqNum,
341            inst->disassemble(instPC.instAddr()), instPC);
342
343    void *bp_history = NULL;
344
345    if (inst->isUncondCtrl()) {
346        DPRINTF(Branch, "[tid:%i] Unconditional control.\n", tid);
347        pred_taken = true;
348        // Tell the BP there was an unconditional branch.
349        uncondBranch(instPC.instAddr(), bp_history);
350
351        if (inst->isReturn() && RAS[tid].empty()) {
352            DPRINTF(Branch, "[tid:%i] RAS is empty, predicting "
353                    "false.\n", tid);
354            pred_taken = false;
355        }
356    } else {
357        ++condPredicted;
358
359        pred_taken = lookup(predPC.instAddr(), bp_history);
360    }
361
362    PredictorHistory predict_record(seqNum, predPC.instAddr(), pred_taken,
363                                    bp_history, tid);
364
365    // Now lookup in the BTB or RAS.
366    if (pred_taken) {
367        if (inst->isReturn()) {
368            ++usedRAS;
369
370            // If it's a function return call, then look up the address
371            // in the RAS.
372            TheISA::PCState rasTop = RAS[tid].top();
373            target = TheISA::buildRetPC(instPC, rasTop);
374
375            // Record the top entry of the RAS, and its index.
376            predict_record.usedRAS = true;
377            predict_record.RASIndex = RAS[tid].topIdx();
378            predict_record.RASTarget = rasTop;
379
380            assert(predict_record.RASIndex < 16);
381
382            RAS[tid].pop();
383
384            DPRINTF(Branch, "[tid:%i]: Instruction %s is a return, "
385                    "RAS predicted target: %s, RAS index: %i.\n",
386                    tid, instPC, target,
387                    predict_record.RASIndex);
388        } else {
389            ++BTBLookups;
390
391            if (inst->isCall()) {
392
393                RAS[tid].push(instPC);
394                predict_record.pushedRAS = true;
395
396                // Record that it was a call so that the top RAS entry can
397                // be popped off if the speculation is incorrect.
398                predict_record.wasCall = true;
399
400                DPRINTF(Branch, "[tid:%i]: Instruction %s was a call"
401                        ", adding %s to the RAS index: %i.\n",
402                        tid, instPC, predPC,
403                        RAS[tid].topIdx());
404            }
405
406            if (inst->isCall() &&
407                inst->isUncondCtrl() &&
408                inst->isDirectCtrl()) {
409                target = inst->branchTarget(instPC);
410            } else if (BTB.valid(predPC.instAddr(), asid)) {
411                ++BTBHits;
412
413                // If it's not a return, use the BTB to get the target addr.
414                target = BTB.lookup(predPC.instAddr(), asid);
415
416                DPRINTF(Branch, "[tid:%i]: [asid:%i] Instruction %s "
417                        "predicted target is %s.\n",
418                        tid, asid, instPC, target);
419            } else {
420                DPRINTF(Branch, "[tid:%i]: BTB doesn't have a "
421                        "valid entry, predicting false.\n",tid);
422                pred_taken = false;
423            }
424        }
425    }
426
427    if (pred_taken) {
428        // Set the PC and the instruction's predicted target.
429        predPC = target;
430    }
431    DPRINTF(Branch, "[tid:%i]: [sn:%i]: Setting Predicted PC to %s.\n",
432            tid, seqNum, predPC);
433
434    predHist[tid].push_front(predict_record);
435
436    DPRINTF(Branch, "[tid:%i] [sn:%i] pushed onto front of predHist "
437            "...predHist.size(): %i\n",
438            tid, seqNum, predHist[tid].size());
439
440    return pred_taken;
441}
442
443void
444BPredUnit::update(const InstSeqNum &done_sn, ThreadID tid)
445{
446    DPRINTF(Branch, "[tid:%i]: Committing branches until "
447            "[sn:%lli].\n", tid, done_sn);
448
449    iPred.commit(done_sn, tid);
450    while (!predHist[tid].empty() &&
451           predHist[tid].back().seqNum <= done_sn) {
452        // Update the branch predictor with the correct results.
453        if (!predHist[tid].back().wasSquashed) {
454            update(predHist[tid].back().pc, predHist[tid].back().predTaken,
455                predHist[tid].back().bpHistory, false);
456        } else {
457            retireSquashed(predHist[tid].back().bpHistory);
458        }
459
460        predHist[tid].pop_back();
461    }
462}
463
464void
465BPredUnit::squash(const InstSeqNum &squashed_sn, ThreadID tid)
466{
467    History &pred_hist = predHist[tid];
468
469    iPred.squash(squashed_sn, tid);
470    while (!pred_hist.empty() &&
471           pred_hist.front().seqNum > squashed_sn) {
472        if (pred_hist.front().usedRAS) {
473            DPRINTF(Branch, "[tid:%i]: Restoring top of RAS to: %i,"
474                    " target: %s.\n", tid,
475                    pred_hist.front().RASIndex, pred_hist.front().RASTarget);
476
477            RAS[tid].restore(pred_hist.front().RASIndex,
478                             pred_hist.front().RASTarget);
479        } else if (pred_hist.front().wasCall && pred_hist.front().pushedRAS) {
480             // Was a call but predicated false. Pop RAS here
481             DPRINTF(Branch, "[tid: %i] Squashing"
482                     "  Call [sn:%i] PC: %s Popping RAS\n", tid,
483                     pred_hist.front().seqNum, pred_hist.front().pc);
484             RAS[tid].pop();
485        }
486
487        // This call should delete the bpHistory.
488        squash(pred_hist.front().bpHistory);
489
490        DPRINTF(Branch, "[tid:%i]: Removing history for [sn:%i] "
491                "PC %s.\n", tid, pred_hist.front().seqNum,
492                pred_hist.front().pc);
493
494        pred_hist.pop_front();
495
496        DPRINTF(Branch, "[tid:%i]: predHist.size(): %i\n",
497                tid, predHist[tid].size());
498    }
499}
500
501void
502BPredUnit::squash(const InstSeqNum &squashed_sn,
503                  const TheISA::PCState &corrTarget,
504                  bool actually_taken, ThreadID tid)
505{
506    // Now that we know that a branch was mispredicted, we need to undo
507    // all the branches that have been seen up until this branch and
508    // fix up everything.
509    // NOTE: This should be call conceivably in 2 scenarios:
510    // (1) After an branch is executed, it updates its status in the ROB
511    //     The commit stage then checks the ROB update and sends a signal to
512    //     the fetch stage to squash history after the mispredict
513    // (2) In the decode stage, you can find out early if a unconditional
514    //     PC-relative, branch was predicted incorrectly. If so, a signal
515    //     to the fetch stage is sent to squash history after the mispredict
516
517    History &pred_hist = predHist[tid];
518
519    ++condIncorrect;
520    ppMisses->notify(1);
521
522    DPRINTF(Branch, "[tid:%i]: Squashing from sequence number %i, "
523            "setting target to %s.\n", tid, squashed_sn, corrTarget);
524
525    // Squash All Branches AFTER this mispredicted branch
526    squash(squashed_sn, tid);
527
528    // If there's a squash due to a syscall, there may not be an entry
529    // corresponding to the squash.  In that case, don't bother trying to
530    // fix up the entry.
531    if (!pred_hist.empty()) {
532
533        auto hist_it = pred_hist.begin();
534        //HistoryIt hist_it = find(pred_hist.begin(), pred_hist.end(),
535        //                       squashed_sn);
536
537        //assert(hist_it != pred_hist.end());
538        if (pred_hist.front().seqNum != squashed_sn) {
539            DPRINTF(Branch, "Front sn %i != Squash sn %i\n",
540                    pred_hist.front().seqNum, squashed_sn);
541
542            assert(pred_hist.front().seqNum == squashed_sn);
543        }
544
545
546        if ((*hist_it).usedRAS) {
547            ++RASIncorrect;
548            DPRINTF(Branch, "[tid:%i]: Incorrect RAS [sn:%i]\n",
549                    tid, hist_it->seqNum);
550        }
551
552        // Have to get GHR here because the update deletes bpHistory
553        unsigned ghr = getGHR(hist_it->bpHistory);
554
555        update((*hist_it).pc, actually_taken,
556               pred_hist.front().bpHistory, true);
557        hist_it->wasSquashed = true;
558
559        if (actually_taken) {
560            if (hist_it->wasReturn && !hist_it->usedRAS) {
561                 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
562                         "  return [sn:%i] PC: %s\n", tid, hist_it->seqNum,
563                         hist_it->pc);
564                 RAS[tid].pop();
565                 hist_it->usedRAS = true;
566            }
567            if (hist_it->wasIndirect) {
568                ++indirectMispredicted;
569                iPred.recordTarget(hist_it->seqNum, ghr, corrTarget, tid);
570            } else {
571                DPRINTF(Branch,"[tid: %i] BTB Update called for [sn:%i]"
572                        " PC: %s\n", tid,hist_it->seqNum, hist_it->pc);
573
574                BTB.update((*hist_it).pc, corrTarget, tid);
575            }
576        } else {
577           //Actually not Taken
578           if (hist_it->usedRAS) {
579                DPRINTF(Branch,"[tid: %i] Incorrectly predicted"
580                        "  return [sn:%i] PC: %s Restoring RAS\n", tid,
581                        hist_it->seqNum, hist_it->pc);
582                DPRINTF(Branch, "[tid:%i]: Restoring top of RAS"
583                        " to: %i, target: %s.\n", tid,
584                        hist_it->RASIndex, hist_it->RASTarget);
585                RAS[tid].restore(hist_it->RASIndex, hist_it->RASTarget);
586                hist_it->usedRAS = false;
587           } else if (hist_it->wasCall && hist_it->pushedRAS) {
588                 //Was a Call but predicated false. Pop RAS here
589                 DPRINTF(Branch, "[tid: %i] Incorrectly predicted"
590                         "  Call [sn:%i] PC: %s Popping RAS\n", tid,
591                         hist_it->seqNum, hist_it->pc);
592                 RAS[tid].pop();
593                 hist_it->pushedRAS = false;
594           }
595        }
596    } else {
597        DPRINTF(Branch, "[tid:%i]: [sn:%i] pred_hist empty, can't "
598                "update.\n", tid, squashed_sn);
599    }
600}
601
602void
603BPredUnit::dump()
604{
605    int i = 0;
606    for (const auto& ph : predHist) {
607        if (!ph.empty()) {
608            auto pred_hist_it = ph.begin();
609
610            cprintf("predHist[%i].size(): %i\n", i++, ph.size());
611
612            while (pred_hist_it != ph.end()) {
613                cprintf("[sn:%lli], PC:%#x, tid:%i, predTaken:%i, "
614                        "bpHistory:%#x\n",
615                        pred_hist_it->seqNum, pred_hist_it->pc,
616                        pred_hist_it->tid, pred_hist_it->predTaken,
617                        pred_hist_it->bpHistory);
618                pred_hist_it++;
619            }
620
621            cprintf("\n");
622        }
623    }
624}
625
626